[백준] 4179번 : 불!

문제

지훈이가 불에 타기 전에 미로를 탈출할 수 있으면

탈출 시간을 출력하고 불가능하다면 IMPOSSIBE을 출력하는 문제로

불은 매시간 상하좌우 4방향으로 한 칸씩 확산되고

지훈이는 상하좌우 한 칸씩 이동할 수 있다.

 

(지훈이와 불은 모두 벽을 통과할 수는 없다)

 

접근 방식

지훈이와 불을 동시에 출발시켜서 지훈이가 미로를 탈출하는지를

확인하면 되는 문제로 접근 방식을 떠올리는 건 간단한 문제다.

 

이제 어떻게 동시에 출발 시키냐는건데

일단 반복문에서 동시에 불과 지훈이를 한 번에

같이 탐색하는 건 불가능하다. (추후에 백트래킹을 배우면 가능하다.)

 

그래서 불과 지훈이를 각각 따로 움직여서 기록을 남길 건데,

이전에 풀어왔던 BFS 문제들처럼 거리를 남겨주면 된다.

 

불들의 거리를 모두 남긴 이후에 지훈이를 출발시켜서

불보다 짧으면 갈 수 있게 만들면 된다.

 

그리고 미로를 탈출한다는 것은 지훈이의 좌표가

배열의 범위를 벗어났다는 것을 확인해 주면 된다.

 

문제의 접근 자체는 쉬웠지만 풀이가 오래 걸렸던 문제인데

불이 하나가 아니라 여러 개라는 것을 조심해야 한다.

(이걸 몰라서 시간 잡아먹었다... 문제에 왜 안 적혀있는 건지...)

 

풀이

public class Main {

	private static int[] dx = {1, 0, -1, 0};
	private static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int r = Integer.parseInt(st.nextToken()); // n
		int c = Integer.parseInt(st.nextToken()); // m

		char[][] maze = new char[r][c];
		int[][] fireDistances = new int[r][c];
		int[][] jihunDistances = new int[r][c];

		Queue<Pair> fireQueue = new ArrayDeque<>();
		Queue<Pair> jihunQueue = new ArrayDeque<>();

		for (int i = 0; i < r; i++) {
			char[] input = br.readLine().toCharArray();

			for (int j = 0; j < c; j++) {
				maze[i][j] = input[j];

				jihunDistances[i][j] = -1;
				fireDistances[i][j] = -1;

				if (input[j] == 'J') {
					jihunDistances[i][j] = 0;
					jihunQueue.offer(new Pair(i, j));
				} else if (input[j] == 'F') {
					fireDistances[i][j] = 0;
					fireQueue.offer(new Pair(i, j));
				}
			}
		}

		while (!fireQueue.isEmpty()) {
			Pair cur = fireQueue.poll();

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (fireDistances[nx][ny] >= 0 || maze[nx][ny] == '#') continue;

				fireDistances[nx][ny] = fireDistances[cur.x][cur.y] + 1;
				fireQueue.offer(new Pair(nx, ny));
			}
		}

		while (!jihunQueue.isEmpty()) {
			Pair cur = jihunQueue.poll();

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
					System.out.println(jihunDistances[cur.x][cur.y] + 1);
					return;
				}
				if (jihunDistances[nx][ny] >= 0 || maze[nx][ny] == '#') continue;
				if (fireDistances[nx][ny] != -1 && jihunDistances[cur.x][cur.y] + 1 >= fireDistances[nx][ny]) continue;

				jihunDistances[nx][ny] = jihunDistances[cur.x][cur.y] + 1;
				jihunQueue.offer(new Pair(nx, ny));
			}
		}

		System.out.println("IMPOSSIBLE");
	}

	private static class Pair {
		int x;
		int y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}