BOJ 4179 불!

https://www.acmicpc.net/problem/4179

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

---

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

---

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

---

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

---

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static int R;
    static int C;
    static int[] dirR = {0, 0, 1, -1};
    static int[] dirC = {1, -1, 0, 0};
    static char[][] map;
    static Deque<Point> jihun = new ArrayDeque<>();
    static Deque<Point> fire = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = (char) br.read();
                if(map[i][j] == 'F') {
                    fire.offer(new Point(i, j));
                } else if (map[i][j] == 'J') {
                    jihun.offer(new Point(i, j));
                }
            }
            br.readLine();
        }

        int time = 1;
        for (; !jihun.isEmpty(); time++) {
            boolean result = escape();
            
            // 현재 시간에서 탈출 가능한 경우, 시간을 출력 후 종료
            if(result) {
                System.out.println(time);
                return;
            }
        }
        
        System.out.println("IMPOSSIBLE");
    }

    // 탈출 가능한지 탐색 후 가능하면 true, 아니면 false 반환
    static boolean escape() {
        int jihunSize = jihun.size();
        int fireSize = fire.size();

        // 현재 시간에서 지훈이가 움직일 수 있는 곳을 탐색
        for (int i = 0; i < jihunSize; i++) {
            Point check = jihun.poll();

            // 이전 시간에 지훈이가 움직인 곳이 불에 타버렸을 때, 탐색 스킵
            if(map[check.x][check.y] == 'F') {
                continue;
            }

            for (int j = 0; j < dirR.length; j++) {
                int newRow = check.x + dirR[j];
                int newCol = check.y + dirC[j];

                if(newRow < 0 || newCol < 0 || newRow == R || newCol == C) {
                    return true;
                }

                if(map[newRow][newCol] == '.') {
                    map[newRow][newCol] = 'J';
                    jihun.offer(new Point(newRow, newCol));
                }
            }
        }

        // 현재 시간에서 불이 옮겨 붙을 수 있는 곳 탐색
        for (int i = 0; i < fireSize; i++) {
            Point check = fire.poll();

            for (int j = 0; j < dirR.length; j++) {
                int newRow = check.x + dirR[j];
                int newCol = check.y + dirC[j];
                boolean isInside = newRow >= 0 && newRow < R && newCol >= 0 && newCol < C;

                if(isInside && map[newRow][newCol] != '#' && map[newRow][newCol] != 'F') {
                    map[newRow][newCol] = 'F';
                    fire.offer(new Point(newRow, newCol));
                }
            }
        }

        return false;
    }
}