[백준] 5427번 불(BFS)

https://www.acmicpc.net/problem/5427

풀이

이 문제는 그래프 탐색 문제로, 상근이와 불의 이동을 동시에 처리해야 합니다. 상근이가 건물에서 가장 빠르게 탈출할 수 있는 시간을 구하는 문제입니다. 불은 매 초마다 확산되기 때문에, 불이 퍼지기 전에 상근이가 탈출해야 합니다. 만약 불이 먼저 도달하거나 탈출할 방법이 없으면 "IMPOSSIBLE"을 출력해야 합니다.

문제 해결 전략

1. 불과 상근이의 이동을 동시에 처리:
   • 불이 확산되면서 상근이도 동시에 움직입니다. 상근이가 불이 퍼진 칸 또는 퍼질 예정인 칸으로 이동할 수 없다는 조건이 있으므로, 불의 이동을 먼저 계산하고 그다음에 상근이의 이동을 처리해야 합니다.
   • BFS(너비 우선 탐색)를 사용하여 불의 확산과 상근이의 이동을 동시에 처리할 수 있습니다. BFS는 최단 경로를 구하는 데 유리한 탐색 방법입니다.
2. BFS로 불과 상근이의 이동 처리:
   • 먼저 불이 퍼지는 칸을 BFS로 확산시킵니다.
   • 상근이는 불이 퍼진 칸이나 퍼질 예정인 칸으로 이동할 수 없으므로, BFS로 상근이의 이동을 처리할 때 불의 이동을 고려해야 합니다.
   • 상근이가 빌딩의 가장자리(경계선)에 도착하면 탈출할 수 있습니다. 이 경우 탈출 시간을 기록합니다.
3. 탐색이 불가능한 경우:
   • 상근이가 탈출할 수 없을 경우 IMPOSSIBLE을 출력합니다.

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

public class Main {
    static int w, h;
    static char[][] building;
    static int[][] fireTime;   // 불이 도착하는 시간
    static int[][] personTime; // 상근이가 도착하는 시간
    static Queue<int[]> fireQueue;   // 불의 위치를 저장하는 큐
    static Queue<int[]> personQueue; // 상근이의 위치를 저장하는 큐

    // 상, 하, 좌, 우 이동을 위한 방향 벡터
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken()); // 빌딩의 너비
            h = Integer.parseInt(st.nextToken()); // 빌딩의 높이
            
            building = new char[h][w];
            fireTime = new int[h][w];    // 불이 해당 칸에 도착하는 시간
            personTime = new int[h][w];  // 상근이가 해당 칸에 도착하는 시간
            fireQueue = new LinkedList<>();
            personQueue = new LinkedList<>();

            // 배열 초기화
            for (int i = 0; i < h; i++) {
                Arrays.fill(fireTime[i], -1);   // 불 도착 시간을 -1로 초기화
                Arrays.fill(personTime[i], -1); // 상근이 도착 시간을 -1로 초기화
            }

            // 입력 처리
            for (int i = 0; i < h; i++) {
                String line = br.readLine();
                for (int j = 0; j < w; j++) {
                    building[i][j] = line.charAt(j);

                    if (building[i][j] == '*') {  // 불이 시작되는 위치
                        fireQueue.offer(new int[]{i, j});
                        fireTime[i][j] = 0; // 불이 있는 칸의 도착 시간을 0으로 설정
                    } else if (building[i][j] == '@') { // 상근이의 시작 위치
                        personQueue.offer(new int[]{i, j});
                        personTime[i][j] = 0; // 상근이의 시작 시간도 0으로 설정
                    }
                }
            }

            // 불의 확산 BFS
            spreadFire();
            // 상근이의 이동 BFS
            int result = movePerson();

            // 결과 출력
            if (result == -1) {
                System.out.println("IMPOSSIBLE");
            } else {
                System.out.println(result);
            }
        }
    }

    // 불의 확산을 처리하는 BFS
    static void spreadFire() {
        while (!fireQueue.isEmpty()) {
            int[] cur = fireQueue.poll();
            int x = cur[0];
            int y = cur[1];

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

                if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
                    if (building[nx][ny] == '.' && fireTime[nx][ny] == -1) {
                        fireTime[nx][ny] = fireTime[x][y] + 1;
                        fireQueue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

    // 상근이의 이동을 처리하는 BFS
    static int movePerson() {
        while (!personQueue.isEmpty()) {
            int[] cur = personQueue.poll();
            int x = cur[0];
            int y = cur[1];

            // 상근이가 경계에 도착하면 탈출 성공
            if (x == 0 || x == h - 1 || y == 0 || y == w - 1) {
                return personTime[x][y] + 1; // 경계에서 탈출하므로 +1초
            }

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

                if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
                    if (building[nx][ny] == '.' && personTime[nx][ny] == -1) {
                        // 불이 도착하는 시간보다 먼저 이동할 수 있어야 함
                        if (fireTime[nx][ny] == -1 || fireTime[nx][ny] > personTime[x][y] + 1) {
                            personTime[nx][ny] = personTime[x][y] + 1;
                            personQueue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
        return -1; // 탈출할 수 없는 경우
    }
}

코드 설명

1. 입력 처리:
   • 여러 테스트 케이스에 대한 입력을 처리하며, 빌딩의 높이 h, 너비 w 및 빌딩의 지도 정보를 입력받습니다.
   • 각 테스트 케이스마다 building[][], fireTime[][], personTime[][] 배열을 초기화하고, 불(`)과 상근이(@`)의 위치를 큐에 추가합니다.
2. 불의 확산 BFS:
   • spreadFire() 함수는 불이 확산되는 과정을 BFS로 처리합니다. 각 불이 인접한 칸으로 확산되며, 해당 칸에 도착하는 시간을 기록합니다.
   • 불이 벽('#')이나 이미 확산된 곳은 확산하지 않습니다.
3. 상근이의 이동 BFS:
   • movePerson() 함수는 상근이의 이동을 BFS로 처리합니다. 상근이는 빈 공간(.)으로만 이동할 수 있으며, 불이 도착하는 시간보다 먼저 해당 칸에 도착할 수 있어야 합니다.
   • 상근이가 빌딩의 경계에 도달하면 탈출 성공으로, 그때까지 걸린 시간을 반환합니다.
   • 만약 탈출할 수 없으면 1을 반환합니다.
4. 불과 상근이의 시간 비교:
   • 상근이가 이동할 칸의 시간(personTime)과 불이 그 칸에 도착하는 시간(fireTime)을 비교하여, 상근이가 불보다 먼저 도착할 수 있을 때만 이동이 가능합니다.

시간 복잡도 분석

1. 불의 확산 BFS:
   • 불의 확산 BFS는 불이 퍼질 수 있는 모든 칸을 탐색하며, 각 칸을 한 번씩만 방문하므로 O(w * h)의 시간이 소요됩니다.
2. 상근이의 이동 BFS:
   • 상근이의 이동 BFS 역시 빈 공간을 탐색하며, 각 칸을 한 번씩 방문하므로 O(w * h)의 시간이 소요됩니다.
3. 전체 시간 복잡도:
   • 각 테스트 케이스에 대해 불과 상근이의 이동을 처리하므로, 한 테스트 케이스에 대한 시간 복잡도는 O(w * h)입니다.
   • 테스트 케이스가 최대 100개이므로, 전체 시간 복잡도는