[백준] 5427. 불

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

5427번: 불

bfs 문제로 크게 막힘없이 풀 수 있었다. 다만 주의할 점과 내가 놓친 부분은 다음과 같다.

• 상근이는 불이 붙으려는 칸으로 이동할 수 없다. 그리고 상근이가 있는 칸에 불이 옮겨옴과 동시에 상근이가 다른 칸으로 이동할 수 있다. 따라서 불이 먼저 이동하고, 상근이가 이동해야 한다.
• 불과 상근은 시간 당 한 칸씩 이동할 수 있다. 따라서 fireQue.size()만큼 각 불들이 한 칸씩 이동하도록 하고, personQue.size()만큼 각 상근이가 한 칸씩 이동하도록 해야 한다. 
• 상근이가 4방면으로 각각 이동할 수 있다. 이는 personQue가 있는 이유이기도 하다. 따라서 탈출하는데 걸리는 시간을 int answer과 같이 하나의 변수로 두고 변수 값을 증가시키는 식으로 하면 안된다. 사방면으로 이동할 때, 4개의 위치에 있는 상근은 각각의 경우인거지, 4번에 걸쳐 이동한 것이 아니기 때문이다. 따라서 각 위치로 이동하는데 걸리는 시간을 나타내는 time[][] 배열을 두었다.

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

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

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

    static int t;
    static int w;
    static int h;
    static String[][] map;
    static int[][] time;
    static Queue<Point> fireQue;
    static Queue<Point> personQue;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            fireQue = new LinkedList<>();
            personQue = new LinkedList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new String[h][w];
            time = new int[h][w];

            // 그래프 초기화
            for (int j = 0; j < h; j++) {
                String[] input = br.readLine().split("");
                for (int k = 0; k < w; k++) {
                    map[j][k] = input[k];
                    if (map[j][k].equals("*")) {
                        fireQue.add(new Point(j, k));
                    }
                    if (map[j][k].equals("@")) {
                        personQue.add(new Point(j, k));
                    }
                }
            }

            // bfs
            bfs();
        }
    }

    private static void bfs() {

        // 더 이상 움직일 수 없을 때까지
        while (!personQue.isEmpty()) {

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

                    // 그래프 밖 / 벽 / 이미 방문한 곳 ->  불 번지기 X
                    if (nx < 0 || nx >= w || ny < 0 || ny >= h || map[ny][nx].equals("#") || map[ny][nx].equals("*")) {
                        continue;
                    }

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

            // 사람 이동
            int personSize = personQue.size();
            for (int i = 0; i < personSize; i++) {
                Point person = personQue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = person.x + dx[j];
                    int ny = person.y + dy[j];

                    // 탈출
                    if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
                        System.out.println(time[person.y][person.x] + 1);
                        return;
                    }

                    // 빈 공간일 때만 이동 가능 (불, 벽, 이미 이동한 공간이면 pass)
                    if (map[ny][nx].equals(".")) {
                        map[ny][nx] = "@";
                        personQue.add(new Point(ny, nx));
                        time[ny][nx] = time[person.y][person.x] + 1;
                    }
                }
            }
        }

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

    static class Point {
        int y, x;

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