문제

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

접근

가장 빠른 탈출 시간을 구해야 하니 BFS 문제임을 알 수 있다.
문제 번역이 개똥같이 되어 있어서 문제를 푸는 데보다 이해하는데 더 오래 걸렸다;;
막상 보니 별 거 없더라...
지훈이가 처음부터 가장자리에 있는 경우만 잘 처리해주면 됐다.

구현

import java.io.*;
import java.util.*;

class Main {
    static int R;
    static int C;
    static char[][] maze;
    static List<int[]> fires = new ArrayList<>();
    static int[] dx = {-1, 0, 1, 0};
    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());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        maze = new char[R][C];
        boolean[][] visited = new boolean[R][C];
        int startR = 0;
        int startC = 0;
        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                maze[i][j] = input.charAt(j);
                if (maze[i][j] == 'J') {
                    startR = i;
                    startC = j;
                    maze[i][j] = '.';
                } else if (maze[i][j] == 'F') {
                    fires.add(new int[] {i, j});
                }
            }
        }

        if (startR == 0 || startR == R - 1 || startC == 0 || startC == C - 1) {
            System.out.println(1);
            return;
        }

        Queue<Info> queue = new LinkedList<>();
        int minute = 0;
        queue.offer(new Info(minute, startR, startC));
        visited[startR][startC] = true;
        spreadFire();
        while (!queue.isEmpty()) {
            Info info = queue.poll();
            if (info.minute > minute) {
                minute++;
                spreadFire();
            }
            for (int k = 0; k < 4; k++) {
                int nextR = info.jRow + dx[k];
                int nextC = info.jCol + dy[k];
                if (nextR >= 0 && nextR < R && nextC >= 0 && nextC < C && maze[nextR][nextC] == '.' && !visited[nextR][nextC]) {
                    if (nextR == 0 || nextR == R - 1 || nextC == 0 || nextC == C - 1) {
                        System.out.println(minute + 2);
                        return;
                    }
                    visited[nextR][nextC] = true;
                    queue.offer(new Info(minute + 1, nextR, nextC));
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

    private static void spreadFire() {
        List<int[]> spreaded = new ArrayList<>();
        for (int[] fire : fires) {
            for (int k = 0; k < 4; k++) {
                int nextR = fire[0] + dx[k];
                int nextC = fire[1] + dy[k];
                if (nextR >= 0 && nextR < R && nextC >= 0 && nextC < C && maze[nextR][nextC] == '.') {
                    maze[nextR][nextC] = 'F';
                    spreaded.add(new int[] {nextR, nextC});
                }
            }
        }
        fires.clear();
        fires.addAll(spreaded);
    }

    static class Info {
        int minute;
        int jRow;
        int jCol;
        Info (int minute, int jRow, int jCol) {
            this.minute = minute;
            this.jRow = jRow;
            this.jCol = jCol;
        }
    }
}