(5427) 불 (Java)

문제

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

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

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

입력

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

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

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

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.

출력

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

예제 입력 1

5
4 3
####
#@.
####
\7 6
###.###
##.##
#.....#
#.....#
#..@..#
#######
\7 4
###.###
#....#
#@....#
.######
\5 5
.....
..
.@.
..
.....
\3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2012 F번

문제의 오타를 찾은 사람: adh0463
데이터를 추가한 사람: b8goal, djm03178
문제를 번역한 사람: baekjoon

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색

Solution

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

public class Main {
    public static int tc, w, h;
    public static char[][] bd;
    public static int[][] fire;
    public static int[][] sg;
    public static int dx[] = {1, 0, -1, 0};
    public static int dy[] = {0, -1, 0, 1};

    public static class Pair {
        int x, y;

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

    public static Queue<Pair> qFire;
    public static Queue<Pair> qSg;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        tc = Integer.parseInt(br.readLine());

        for(int t = 0; t < tc; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            // 불 번짐 탐색을 위한 큐 생성
            qFire = new LinkedList<Pair>();
            // 상근 이동위치 탐색을 위한 큐 생성
            qSg = new LinkedList<Pair>();

            // 빌딩, 불, 상근 세팅
            bd = new char[h][w];
            fire = new int[h][w];
            sg = new int[h][w];

            for(int i = 0; i < h; i++) {
                String[] strArr = br.readLine().split("");
                for(int j = 0; j < w; j++) {
                    char ch = strArr[j].charAt(0);
                    
                    // 빌딩 도면 생성
                    bd[i][j] = ch;

                    // 불 시작 위치, 시간 세팅
                    if(ch == '*') {
                        qFire.offer(new Pair(i, j));
                        fire[i][j] = 0;
                    } else {
                        fire[i][j] = -1;
                    }
                    
                    // 상근이 시작 위치, 시간 세팅
                    if(ch == '@') {
                        qSg.offer(new Pair(i, j));
                        sg[i][j] = 0;
                    } else {
                        sg[i][j] = -1;
                    }
                }
            }

            // 빌딩 탈출
            bw.write(findEscape() + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static String findEscape() {
        // 불의 번짐 탐색
        while(!qFire.isEmpty()) {
            Pair pollCell = qFire.poll();

            // 인접 칸 탐색
            for(int k = 0; k < 4; k++) {
                int nx = pollCell.x + dx[k];
                int ny = pollCell.y + dy[k];
                
                // 빌딩 범위를 벗어나거나, 벽이거나, 이미 불이 번져있으면 skip
                if(isNotRange(nx, ny) || bd[nx][ny] == '#' || fire[nx][ny] != -1) continue;
                
                // 불 번짐
                qFire.offer(new Pair(nx, ny));
                fire[nx][ny] = fire[pollCell.x][pollCell.y] + 1;    // 불 번짐 시간 +1초
            }
        }
        
        // 상근 이동 탐색
        while(!qSg.isEmpty()) {
            Pair pollCell = qSg.poll();

            // 상근이가 빌딩 범위를 벗어나면 탈출
            // 즉, 현재 위치가 빌딩의 가장자리이면 탈출
            if(isEdge(pollCell.x, pollCell.y)) return String.valueOf(sg[pollCell.x][pollCell.y] + 1);

            // 인접 칸 탐색
            for(int k = 0; k < 4; k++) {
                int nx = pollCell.x + dx[k];
                int ny = pollCell.y + dy[k];

                // 빌딩 범위를 벗어나거나, 벽이거나, 이미 상근이가 지나간 자리이거나,
                // 상근이 도착 시점에 불이 이미 번져있으면 skip
                if(isNotRange(nx, ny) || bd[nx][ny] == '#' || sg[nx][ny] != -1
                        || (fire[nx][ny] != -1 && fire[nx][ny] <= sg[pollCell.x][pollCell.y]+1)) continue;
                
                // 상근 이동
                qSg.offer(new Pair(nx, ny));
                sg[nx][ny] = sg[pollCell.x][pollCell.y] + 1;    // 상근 이동 시간 +1초
            }
        }
        
        // 상근이가 이동 중에 탈출을 못했으므로
        return "IMPOSSIBLE";
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= h || y < 0 || y >= w) ? true : false;
    }

    public static boolean isEdge(int x, int y) {
        return (x == 0 || x == h-1 || y == 0 || y == w-1) ? true : false;
    }
}

Feedback

상근 이동 탐색 과정 중 poll 한 원소가 가장자리인 것을 체크하더라도, 아래의 인접 칸 탐색 과정에서 빌딩 범위를 벗어난 칸에 대한 validation은 해주어야 한다. 이유는.. 솔직히 잘 모르겠다.. IndexOutOfBounds 에러가 발생하는데..