[백준] 4179. 불!

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

4179번: 불!

bfs 문제인데 이 문제를 풀며 주의할 점이 몇가지 있다.

• 논리적으로 불과 지훈이 동시에 이동해야 한다. 따라서 코드 상으로 불과 지훈이 순차적으로 한 번씩 이동해야 하는데, 둘 중에 불을 먼저 이동시켜야 한다. 불이 먼저 이동해서 불이 번지면, 지훈이가 불이 있는 곳을 피해서 이동해야 하기 때문이다.
• 불을 한 번 이동시킬 때는 fireQue의 사이즈만큼 이동을 처리해주어야 한다. 그래야 그래프에 있는 번져야 하는 불들이 각각 모두 번지게 되는 것이다. 그리고 불이 번지면 그 위치의 값을 "F"로 변경해주어야 한다.
• 마찬가지로 지훈이를 이동시킬 때도 jihoonQue의 사이즈만큼 이동을 처리해주어야 한다. 
• 지훈이가 이동할 수 없는 경우에는 continue로 pass하고, 이동할 수 있으면 그 위치를 johoonQue에 넣어준다. 따라서 지훈이가 더이상 이동할 수 없으면, 즉 jihoonQue가 비면 탈출에 실패한 것이다.

import java.io.BufferedReader;
import java.io.IOException;

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

// 시간복잡도: O(V+E) = 10,000 * 10,000 + 4 * 10,000 * 10,000 = 500,000,000
public class Main {

    static int r;
    static int c;
    static String[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<Position> jihoonQue = new LinkedList<>();
    static Queue<Position> fireQue = new LinkedList<>();
    static boolean[][] jihoonVisited;
    static int answer = 0; // 탈출할 수 있는 가장 빠른 시간

    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 String[r][c];
        jihoonVisited = new boolean[r][c];

        for (int i = 0; i < r; i++) {
            String[] arr = br.readLine().split("");
            for (int j = 0; j < c; j++) {
                map[i][j] = arr[j];
                if (map[i][j].equals("J")) {
                    jihoonQue.add(new Position(i, j));
                    jihoonVisited[i][j] = true;
                }
                if (map[i][j].equals("F")) {
                    fireQue.add(new Position(i, j));
                }
            }
        }

        bfs();
    }

    private static void bfs() {
        // 지훈이 이동할 수 있을 때까지 반복
        while (!jihoonQue.isEmpty()) {

            // 불 이동
            int fireQueSize = fireQue.size();
            for (int i = 0; i < fireQueSize; i++) {
                Position fire = fireQue.poll();
                for (int j = 0; j < 4; j++) {
                    int ny = fire.y + dy[j];
                    int nx = fire.x + dx[j];

                    // 그래프 범위를 넘어가면 pass
                    if (nx < 0 || nx >= c || ny < 0 || ny >= r) {
                        continue;
                    }

                    // 벽이면 번질 수 없고, 이미 불이면 번질 필요 없으므로 pass
                    if (map[ny][nx].equals("#") || map[ny][nx].equals("F")) {
                        continue;
                    }

                    // 불 번지기
                    map[ny][nx] = "F";
                    fireQue.add(new Position(ny, nx));
                }
            }

            // 지훈 이동 
            int jihoonQueSize = jihoonQue.size();
            for (int i = 0; i < jihoonQueSize; i++) {
                Position jihoon = jihoonQue.poll();
                for (int j = 0; j < 4; j++) {
                    int ny = jihoon.y + dy[j];
                    int nx = jihoon.x + dx[j];

                    // 탈출했으면 끝내기
                    if (nx < 0 || nx >= c || ny < 0 || ny >= r) {
                        System.out.println(answer + 1);
                        return;
                    }

                    // 이미 방문했었거나 불이 있거나 벽이면 pass
                    if (jihoonVisited[ny][nx] || map[ny][nx].equals("F") || map[ny][nx].equals("#")) {
                        continue;
                    }

                    // 지훈 이동하기
                    jihoonVisited[ny][nx] = true;
                    jihoonQue.add(new Position(ny, nx));
                }
            }

            answer++;
        }

        // 탈출하지 못하고 더이상 이동이 불가하면 탈출 실패
        System.out.println("IMPOSSIBLE");
    }

    static class Position {
        int y, x;

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