[백준 5427] 불

생각 정리

불을 먼저 bfs 탐색해서, 각 위치에 도착하는데 걸리는 시간을 구한다.
그 다음, 상근이를 bfs 탐색해서 탈출할 수 있을지 확인한다.
상근이 bfs탐색할 때 고려해야 하는 것은

• 상근이가 예전에 해당 위치를 방문했는지
• 상근이가 방문한 곳이 벽인지
• 상근이가 불과 동시 혹은 불보다 늦게 해당 위치를 방문했는지

생각하지 못한 것

• 상근이가 방문한 곳이 '불'인지
• 상근이가 불과 동시 혹은 불보다 늦게 방문한 경우 (불이 해당 위치를 아예 방문하지 않아서 그런 것은 아닌지, 즉 불의 방문 여부도 함께 고민)

코드

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

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


public class Main {
    static int T, w, h;
    static char[][] building;
    static boolean[][] visited, visited2;
    static int[][] dist, fireDist;
    static Queue<Position> queue = new LinkedList<>();
    static Queue<Position> queue2 = new LinkedList<>();
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            building = new char[h][w];
            //방문기록 초기화
            visited = new boolean[h][w];
            visited2 = new boolean[h][w];
            //거리 초기화
            dist = new int[h][w];
            fireDist = new int[h][w];

            for(int j=0; j<h; j++) {
                String str = br.readLine();
                for(int k=0; k<w; k++) {
                    building[j][k] = str.charAt(k);
                    if(building[j][k] == '*') {
                        queue.add(new Position(j, k));
                        visited[j][k] = true;
                    }
                    if(building[j][k] == '@') {
                        queue2.add(new Position(j, k));
                        visited2[j][k] = true;
                    }
                }
            }

            //먼저 불이 퍼져가는 시간 구하기 
            moveFire();

            escape();

            //queue 초기화
            queue = new LinkedList<>();
            queue2 = new LinkedList<>();

        }

    }

    static void moveFire() {
        while(!queue.isEmpty()) {
            Position out = queue.poll();

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

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                else if(visited[nx][ny] || building[nx][ny] == '#') continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    fireDist[nx][ny] = fireDist[out.x][out.y] + 1;
                }
            }
        }
    }

    static void escape() { //불보다 늦게 도착할 때도 넘어가야쥐..
        boolean flag = false;

        while(!queue2.isEmpty()) {
            Position out = queue2.poll();

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

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    System.out.println(dist[out.x][out.y]+1);
                    flag = true;
                    return ;
                }
                else if(visited2[nx][ny] || building[nx][ny] == '#'|| building[nx][ny] == '*') continue;
                else if(fireDist[nx][ny]!= 0 && fireDist[nx][ny] <= dist[out.x][out.y]+1) continue;
                else {
                    queue2.add(new Position(nx, ny));
                    visited2[nx][ny] = true;
                    dist[nx][ny] = dist[out.x][out.y] + 1;
                }
            }

        }

        if(!flag)
            System.out.println("IMPOSSIBLE");
        return ;

    }
    
}