[Java] 백준 5427 불

문제

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

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

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

 

입력

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

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

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

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

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

 

출력

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

 

문제 링크 : [불]

---

설명

전형적인 BFS 문제이다.

 

조금 주의해야할 점은 불이 이동한다는 점.

불이 이동할 예정인 곳에 상근이가 가서는 안된다는 점.

 

불이 이동할 예정인 곳에 가면 안된다는 의미는 불과 같은 시간에 가면 안된다는 의미이다.

불이 4초에 2,0으로 갈 예정일 때, 상근이도 4초에 2,0으로 가는 것은 불가하다는 의미.

 

이 두개만 주의한다면 어려울 것이 없는 문제이다.

 

코드

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

public class Main {
    static char[][] map;  // 지도를 저장
    static int[][] copy;  // 불이 번지는 시간 저장
    static Queue<int[]> q;  // 불과 상근이의 움직임 저장
    static int h, w, ans;  // 행, 열, 정답 시간
    static boolean[][] visit;  // 방문 배열
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t --> 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken()); h = Integer.parseInt(st.nextToken());
            map = new char[h][w]; copy = new int[h][w];
            int x = 0; int y = 0; // 상근이 위치
            for (int i = 0; i < h; i++){
                String s = br.readLine();
                for (int j = 0; j < w; j++){
                    map[i][j] = s.charAt(j);
                    if (map[i][j] == '@'){  // 상근이 위치 저장
                        x = i;
                        y = j;
                    }
                    // 상근이가 갈 수 있지만 불이 못 가는 경우도 있으니 확인 위해 최대 값 지정
                    if (map[i][j] == '.') copy[i][j] = Integer.MAX_VALUE;
                }
            }
            q = new LinkedList<>();
            // 불을 찾는다
            for (int i = 0; i < h; i++){
                for (int j = 0; j < w; j++){
                    if (map[i][j] == '*') q.offer(new int[]{i, j, 0}); // 불 큐에 삽입
                }
            }
            fire(); // 불이 퍼지는 시간 측정
            q.offer(new int[]{x, y, 0}); // 상근이 위치 큐 삽입
            ans = BFS();
            System.out.println(ans == -1 ? "IMPOSSIBLE" : ans);
        }
    }

    private static int BFS() {
        visit = new boolean[h][w]; // 초기화
        while (!q.isEmpty()){
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int cnt = now[2]; // 현재 시간
            visit[x][y]=true;

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

                // 탈출
                if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
                    return cnt + 1;
                }
                if (copy[nx][ny] <= cnt + 1) continue;  // 불이 퍼지는 시간보다 이후일 경우
                if (visit[nx][ny] || map[nx][ny] != '.') continue;  // 이미 방문 했거나 빈 칸이 아닌 경우
                q.offer(new int[]{nx, ny, cnt + 1});
                visit[nx][ny] = true;
            }
        }
        return -1;  // 조건문에서 return 이 되지 않았다면 갈 수 있는 경우가 없음.
    }

    private static void fire() {
        visit = new boolean[h][w];
        while (!q.isEmpty()){
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int cnt = now[2];
            visit[x][y] = true;

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

                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if (visit[nx][ny] || map[nx][ny] == '#') continue; // 벽일 경우

                q.offer(new int[]{nx, ny, cnt + 1});
                visit[nx][ny] = true;
                copy[nx][ny] = cnt + 1;
            }
        }
    }
}