[백준 | Java] 5427 불

내 풀이

상근이가 건물을 탈출할 때 최단 시간을 구하는 것이 목표이므로, 최단 경로를 찾을 수 있는 BFS를 사용해서 풀이했다.
그리고 불이 퍼지는 것과 상근이가 이동하는 것을 동시에 관리해야하기 때문에 여러 출발 지점을 동시에 탐색하는 데 유리한 BFS를 사용했다.

풀이과정은 다음과 같다.

1. 불의 위치를 담은 큐와 상근이의 위치를 담은 큐 입력

2. BFS로 매 초마다 두 큐를 번갈아가며 처리함으로써 두 가지 동작을 동시적으로 시뮬레이션 진행
   a. 불이 옮겨지는 자리엔 상근이는 가지 못하므로, 불의 BFS 먼저 진행
   b. 상근이의 BFS 진행
   c. 두 개의 큐 모두 한 번 탐색이 진행되면 result +1
   d. 상근이의 다음 좌표 중 하나라도 빌딩 밖을 벗어난다면 탐색 종료

3. 결과 출력

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

public class Main {
    static int tc, w, h, result;
    static boolean isExit;
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static Queue<int[]> fireQueue;
    static Queue<int[]> sangQueue;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            map = new char[h][w];
            visited = new boolean[h][w];
            fireQueue = new LinkedList<>();
            sangQueue = new LinkedList<>();
            for (int j = 0; j < h; j++) {
                String tmp = br.readLine();
                for (int k = 0; k < w; k++) {
                    map[j][k] = tmp.charAt(k);
                    if (map[j][k] == '*') fireQueue.add(new int[]{j, k});  // 불의 위치
                    if (map[j][k] == '@') {
                        sangQueue.add(new int[]{j, k});  // 상근이의 위치
                        visited[j][k] = true;
                    }
                }
            }
            isExit = false;
            result = 0;
            getResult();
            if (isExit) {
                System.out.println(result);
            } else {
                System.out.println("IMPOSSIBLE");
            }
        }
    }

    static void getResult() {
        while (!sangQueue.isEmpty()) {
            // 불 bfs
            int fireSize = fireQueue.size();
            for (int i = 0; i < fireSize; i++) {
                int[] fxy = fireQueue.poll();
                for (int j = 0; j < 4; j++) {
                    int fnx = fxy[0] + dx[j];
                    int fny = fxy[1] + dy[j];

                    if (fnx >= 0 && fny >= 0 && fnx < h && fny < w && map[fnx][fny] == '.') {
                        map[fnx][fny] = '*';
                        fireQueue.add(new int[]{fnx, fny});
                    }
                }
            }

            // 상근이 bfs
            int sangSize = sangQueue.size();
            for (int i = 0; i < sangSize; i++) {
                int[] xy = sangQueue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = xy[0] + dx[j];
                    int ny = xy[1] + dy[j];

                    // 빌딩 탈출 조건
                    if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                        isExit = true;
                        result++;
                        return;
                    }

                    if (map[nx][ny] == '.' && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        sangQueue.add(new int[]{nx, ny});
                    }
                }
            }
            result++;
        }
    }
}