문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

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

public class Main {
    static int col, row, cnt;
    static char[][] arr;
    static Queue<Node> q, fire;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        for (int t = 0; t < T; t++) {
            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            col = Integer.parseInt(st.nextToken());
            arr = new char[col][row];

            q = new LinkedList<>();
            fire =  new LinkedList<>();

            for (int i = 0; i < col; i++) {
                st = new StringTokenizer(br.readLine());
                char[] c = st.nextToken().toCharArray();
                for (int j = 0; j < row; j++) {
                    arr[i][j] = c[j];
                    if (c[j] == '@') {
                        q.add(new Node(i, j, 0));
                    }
                    if (c[j] == '*') {
                        fire.add(new Node(i, j));
                    }
                }
            }
            cnt = 0;
            BFS();
            System.out.println(cnt == 0 ? "IMPOSSIBLE" : cnt);

        }
    }
    public static void BFS() {
        int size;
        while (!q.isEmpty()) {
            size = fire.size();
            for (int i = 0; i < size; i++) {
                Node f = fire.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = f.x + dx[j];
                    int ny = f.y + dy[j];
                    if (nx < 0 || ny < 0 || nx >= col || ny >= row)
                        continue;
                    if (arr[nx][ny] == '.' || arr[nx][ny] == '@'){
                        arr[nx][ny] = '*';
                        fire.add(new Node(nx, ny));
                    }
                }
            }

            size = q.size();
            for (int i = 0; i < size; i++) {
                Node n = q.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = n.x + dx[j];
                    int ny = n.y + dy[j];
                    if (nx < 0 || ny < 0 || nx >= col || ny >= row) {
                        cnt = n.dist + 1;
                        return;
                    }
                    if (arr[nx][ny] == '.') {
                        arr[nx][ny] = '@';
                        q.add(new Node(nx, ny, n.dist+1));
                    }
                }
            }
        }
    }
}
class Node {
    int x, y, dist;
    Node (int x, int y) {
        this.x = x;
        this.y = y;
    }
    Node (int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

• 큐 두개를 이용해서 하나는 불, 나머지는 상근이 위치를 파악한다.
• 불을 먼저 이동시키고 상근이를 이동한다.
• nx, ny범위를 벗어나면 탈출했다는 뜻으로 cnt에 이동한 거리(n.dist)를 할당한다.
• 탈출하지 못하면 할당을 받지 못하므로 cnt = 0;