BOJ 4179. 불!

BOJ 4179. 불!

풀이

#, ., J, F로 이루어진 2차원 배열이 주어지고,
주어진 값들은 각각 벽, 지나갈 수 있는 공간, 지훈이의 초기위치, 불이난공간을 의미한다.

불이 상하좌우로 번지므로 불의 전파 경로를 먼저 BFS로 구한다.
불이 번질 때마다 번진시간을 저장한다.

그 다음 지훈이가 이동할 수 있는 경로를 BFS로 구하는데,
지훈이가 특정 칸을 x시간에 방문할 수 있다고 할 때,
그 칸에 x시간이나 그 시간 이전에 불이 전파되었다면, 지훈이는 지나갈 수 없는 경로인 것이다.

지훈이가 주어진 2차원 배열을 벗어날 수 있을 때의 거리 +1을 출력하면 된다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

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

        Queue<int[]> h = new LinkedList<>();
        Queue<int[]> f = new LinkedList<>();
        String[][] board = new String[n][m];
        int[][] hDist = new int[n][m];
        int[][] fDist = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = String.valueOf(s.charAt(j));
                if (board[i][j].equals("#") || board[i][j].equals(".")) {
                    hDist[i][j] = -1;
                    fDist[i][j] = -1;
                }
                if (board[i][j].equals("J")) {
                    h.offer(new int[]{i, j});
                }
                if (board[i][j].equals("F")) {
                    f.offer(new int[]{i, j});
                    hDist[i][j] = -1;
                }
            }
        }
        while (!f.isEmpty()) {
            int[] p = f.poll();
            for (int d = 0; d < 4; d++) {
                int x = p[0] + dx[d];
                int y = p[1] + dy[d];

                if (x < 0 || x >= n || y < 0 || y >= m) continue;
                if (board[x][y].equals("#") || fDist[x][y] > 0) continue;
                f.offer(new int[]{x, y});
                fDist[x][y] = fDist[p[0]][p[1]] + 1;
            }
        }

        while (!h.isEmpty()) {
            int[] p = h.poll();
            for (int d = 0; d < 4; d++) {
                int x = p[0] + dx[d];
                int y = p[1] + dy[d];

                if (x < 0 || x >= n || y < 0 || y >= m) {
                    System.out.println(hDist[p[0]][p[1]] + 1);
                    return;
                }
                if (hDist[x][y] > 0 || board[x][y].equals("#")) continue;
                if (fDist[x][y] != -1 && hDist[p[0]][p[1]] + 1 >= fDist[x][y]) continue;
                h.offer(new int[]{x, y});
                hDist[x][y] = hDist[p[0]][p[1]] + 1;
            }
        }

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