[SWEA] User problem 4727 견우와 직녀 (JAVA)

문제 출처 - SW Expert Academy

문제는 여기

SW Expert Academy

[문제] 

7월 7일은 견우와 직녀가 만나는 날이다.
올 해에도 열심히 일한 견우와 직녀는 서로를 만날 수 있는 그날을 매우매우 설레어하며 기다렸다.
하지만, 직녀가 발목을 다쳤기 때문에 둘이 만나기 위해서는 견우가 직녀가 있는 곳까지 빠르게 달려가는 것이 중요했다.
게다가, 까마귀와 까치에게도 문제가 있었다.
까마귀와 까치는 급속도로 진행된 고령화로 인해서 둘이 한번에 만날수 있을 만큼 커다란 오작교를 만들 수 없는 상태였다.
그래서, 요즘에는 견우와 직녀가 만날 수 있도록 최소한의 다리를 만들어 주는 일만 하고 있었다.
까마귀와 까치는 이마저도 힘들었기 때문에, 1분간 오작교를 만들면 몇 분 동안은 꼭 쉬는 시간을 가져야 했다.
쉬는 시간이 3분과 4분 주기라면, 건널 수 있는 시간은 아래 그림에서 초록색으로 표시된 부분과 같다.

이런 상황에서도 까마귀와 까치는 견우와 직녀를 도와주고 싶었기 때문에, 자신들이 원래 만들던 다리에서 쉬는 시간을 M분 가지는 다리 하나를 더 놓아주겠다고 한다.
다만 아래와 같이 절벽의 가로와 세로로 교차하는 경우에는 까마귀와 까치가 쉬러가기 힘들기 때문에 만들어 줄 수 없다고 한다!

또한, 견우는 최근 고소 공포증이 생겼기 때문에, 오작교를 두 번 연속으로 건너는 일은 없다!
견우는 안그래도 짧은 만남이 이런 악조건에서 더욱 짧아지는것을 원하지 않았다.
그리고 결국, 견우는 이런 까마귀와 까치의 도움으로 최애애애애대한 빠르게 직녀에게 가는 방법을 찾아냈다!
이 때, 견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아라!

[입력]

맨 윗줄에 지도의 크기 N과 새로 설치하는 오작교의 쉬는 시간 주기를 의미하는 M이 주어진다. (2<= N <= 10, 2<= M <= 20)
다음줄 부터는 N*N의 크기를 가지는 지도 정보가 공백을 사이에 두고 주어진다.
각 지도 정보는 다음과 같다.
1: 견우가 이동할 수 있는 길
0: 절벽
1보다 큰 수 : 써있는 수만큼 쉬는 시간의 주기를 가지는 오작교
견우는 0분에 지도 맨 왼쪽위 (0,0)에 위치한다.
직녀는 (N-1, N-1)에 위치한다.

[출력]

이 때 (0,0) 에서 (N-1,N-1)에 도착할 수 있는 최소한의 시간을 구하라!!

단,
이 문제에서는 견우와 직녀가 무조건 만날 수 있는 경우만 주어진다!
또한, 주어지는 맵에서 절벽은 하나 이상 존재한다.

절벽을 한번 건넌 뒤에 곧바로 다른 절벽을 두 번 연속으로 건너는 일은 없다.

 

---

[풀이]

해당 문제는 백준에 있는 문제와 동일하기에 해당 풀이는 아래 링크로 대신한다.

2021.10.19 - [문제 풀이/baekjoon] - [백준] G2 16137번 견우와 직녀 (JAVA)

[백준] G2 16137번 견우와 직녀 (JAVA)

[코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	static int T;
	static int N;
	static int M;
	static int ans;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	// 견우
	static class Altair {
		int x; // 현재 좌표
		int y; // 현재 y좌표
		int t; // 현재까지 걸린 시간
		
		Altair(int x, int y, int t){
			this.x = x;
			this.y = y;
			this.t = t;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			ans = Integer.MAX_VALUE;

			map = new int[N][N];

			for(int r = 0; r < N; r++) {
				st = new StringTokenizer(br.readLine());

				for(int c = 0; c < N; c++) {
					map[r][c] = Integer.parseInt(st.nextToken());
				}
			}

			// 전체 배열을 탐색하면서 절벽인 곳을 찾아
			// 해당 절벽이 교차하는 곳인지를 확인한다.
			// 교차하는 곳이 아니라면 해당 위치에 오작교를 건설하고 탐색
			// 이후 돌아와서 해당 오작교를 다시 절벽으로 만들고 다음에 오는 교차하지 않는 절벽에 오작교 건설 후 탐색
			// 이를 반복하고 최종적으로 가장 적게 걸리는 것이 결과
			for(int r = 0; r < N; r++) {
				for(int c = 0; c < N; c++) {

					// 절별이라면
					if(map[r][c] == 0) {
						boolean[] check = new boolean[4];

						// 사방탐색
						for(int i = 0 ; i < 4 ; i++) {
							int nr = r + dr[i];
							int nc = c + dc[i];

							// 범위를 벗어나면
							if(nr >= N || nr < 0 || nc >= N || nc < 0)
								continue;

							// 탐색하는 곳이 절벽이라면
							if(map[nr][nc] == 0) {
								check[i] = true; // 해당 위치를 절벽으로 체크
							}
						}

						// 현재 절벽을 기준으로 위쪽과 왼쪽이 절벽이면 교차하는 절벽이다.
						if((check[0] && check[2]))
							continue;
						// 현재 절벽을 기준으로 위쪽과 오른쪽이 절벽이면 교차하는 절벽이다.
						else if (check[0] && check[3])
							continue;
						// 현재 절벽을 기준으로 아래쪽과 왼쪽이 절벽이면 교차하는 절벽이다.
						else if (check[1] && check[2])
							continue;
						// 현재 절벽을 기준으로 아래쪽과 오른쪽이 절벽이면 교차하는 절벽이다.
						else if (check[1] && check[3])
							continue;

						map[r][c] = M;
						visited = new boolean[N][N];

						bfs();

						map[r][c] = 0;
					}
				}
			}

			System.out.println("#" + t + " " + ans);
		}
	}
	
	private static void bfs() {
		Queue<Altair> q = new LinkedList<>();
		visited[0][0] = true; // 0, 0에서 시작
		q.offer(new Altair(0, 0, 0));
		
		while(!q.isEmpty()) {
			Altair cur = q.poll();
			
			if(cur.x == N - 1 && cur.y == N - 1) {
				ans = Math.min(ans, cur.t);
				return;
			}
			
			for(int i = 0; i < 4; i++) {
				int nr = cur.x + dr[i];
				int nc = cur.y + dc[i];
				
				// 범위를 벗어나는 경우
				if(nr >= N || nr < 0 || nc >= N || nc < 0)
					continue;
				
				// 갈 수 없는 경우
				if(map[nr][nc] == 0 || visited[nr][nc])
					continue;
				
				// 땅인 경우 이동
				if(map[nr][nc] == 1) {
					visited[nr][nc] = true;
					
					q.offer(new Altair(nr, nc, cur.t + 1));
				}
				
				// 오작교가 생성된 절벽인 경우
				if(map[nr][nc] >= 2 && map[cur.x][cur.y] == 1) {
					// 만약 다음으로 이동을 할 때 시간을 오작교 주기로 나눠서 0이라면 이동 가능 
					if((cur.t + 1) % map[nr][nc] == 0) {
						visited[nr][nc] = true;
						
						q.offer(new Altair(nr, nc, cur.t + 1));
					} else {
						q.offer(new Altair(cur.x, cur.y, cur.t + 1));
					}
				}
			}
		}
	}
}