[Java] 백준 5427 불

백준 5427 불

풀이

빌딩을 탈출할 수 있는 최단 시간을 구해야 하기 때문에 BFS 를 사용하기로 했습니다.

매 초마다 발생하는 일은 상근이의 이동과 불 번짐입니다. 하지만 해당 초에 상근이가 이동하는 경우의 수는 많고 불 번짐은 1회만 발생해야 합니다.

bfs에서는 depth가 같은 point들이 먼저 처리되기 때문에 현재 depth와 queue에서 poll된 point의 depth가 다르다는 건 현재 depth에서 확인할 수 있는 상근이의 이동 경우의 수를 모두 확인했다는 의미이고 불 번짐이 발생해도 된다는 것을 의미합니다.

상근이는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로는 이동할 수 없고 현재 상근이가 있는 칸에 불이 옮겨옴과 동시에 붙이 안 붙은 다른 칸으로 이동할 수는 있기 때문에 상근이의 이동보다 불 번짐을 먼저 처리하였습니다.

상근이가 탈출하였음은 map 배열의 범위를 벗어났을 때로 확인하였습니다.
가장 처음 map 배열의 범위를 벗어난 경우가 정답이기 때문에 바로 bfs 반복문을 벗어날 수 있도록 label을 사용하였습니다.

에러가 났던 부분

구현하며 12%에서 NumberFormat에러가 났습니다.
이유를 찾아보니 입력인 w와 h가 1일 수 있기 때문에 처음에 w == 1 && h == 1인 경우는 map 입력도 받지 않고 바로 1을 출력하고 continue하도록 코드를 짰는데 그럴 경우 다음 케이스의 w, h를 제대로 받지 못하는 문제였습니다.
쉽게 넘어가려다가...ㅎㅎ
w == 1 && h == 1일 때도 map 입력은 받도록 처리함으로써 문제를 해결하였습니다.

코드

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

public class Main {
    static class Point {
        int x;
        int y;
        int depth;

        public Point(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
    static int w, h;
    static char map[][];
    static Point sanggeun;
    static boolean visited[][], fire[][];
    static Deque<Point> firePoint;
    static int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());

        for(int t  = 0;t < tc;t++) {
            String str[] = br.readLine().split(" ");
            w = Integer.parseInt(str[0]);
            h = Integer.parseInt(str[1]);
            
            map = new char[h][w];
            visited = new boolean[h][w];
            fire = new boolean[h][w];
            firePoint = new ArrayDeque<>();
            int ans = 0;

            // 지도 입력 받기
            // 상근이의 위치 저장하고 불 초기 위치 큐에 담기
            for(int i = 0;i < h;i++) {
                map[i] = br.readLine().toCharArray();
                for(int j = 0;j < w;j++) {
                    if(map[i][j] == '@') {
                        sanggeun = new Point(i, j, 1);
                        break;
                    }
                    else if(map[i][j] == '*') {
                        firePoint.add(new Point(i, j, 0));
                        fire[i][j] = true;
                    }
                }
            }

            if(w == 1 && h == 1) {
                System.out.println(1);
                continue;
            }

            Deque<Point> q = new ArrayDeque<>();
            q.add(sanggeun);

            int curDepth = 0;
            
            // 현재 depth와 temp의 depth가 달라지면, 불이 번져야 함
            bfs:
            while(!q.isEmpty()) {
                Point temp = q.poll();

                if(temp.depth != curDepth) {
                    spread();
                    curDepth = temp.depth;
                }

                for(int i = 0;i < 4;i++) {
                    int nx = temp.x + dx[i];
                    int ny = temp.y + dy[i];

                    if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                        ans = temp.depth;
                        break bfs;
                    }
                    else if(visited[nx][ny] || fire[nx][ny] || map[nx][ny] == '#') continue;

                    visited[nx][ny] = true;
                    q.add(new Point(nx, ny, temp.depth + 1));
                }
            }

            if(ans == 0) System.out.println("IMPOSSIBLE");
            else System.out.println(ans);
        }
    }

    static void spread() {
        int size = firePoint.size();
        while(size-- > 0) {
            Point temp = firePoint.poll();

            for(int i = 0;i < 4;i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= h || ny >= w || fire[nx][ny] || map[nx][ny] == '#') continue;

                fire[nx][ny] = true;
                firePoint.add(new Point(nx, ny, 0));
            }
        }
    }
}