4179번: 불!

문제

미로에서 지훈이가 불을 피해 탈출하려고 합니다. 미로의 가장자리에 도달하면 탈출에 성공한 것으로 간주합니다. 지훈이와 불은 매 분마다 상하좌우로 인접한 칸으로 이동(확산)하며, 불은 각 지점에서 네 방향으로 동시에 확산됩니다. 지훈이는 벽이 있는 칸이나 불이 번진 칸, 그리고 불이 번질 예정인 칸으로는 이동할 수 없습니다. 지훈이가 불을 피해 탈출할 수 있는 가장 빠른 시간을 구하는 문제입니다.

• 입력: 첫째 줄에 행의 개수 R과 열의 개수 C가 주어집니다. 다음 R개의 줄에 미로의 상태가 주어집니다. (#: 벽, .: 지나갈 수 있는 공간, J: 지훈이의 초기 위치, F: 불이 난 공간)
• 출력: 탈출할 수 있는 가장 빠른 시간을 출력합니다. 탈출할 수 없다면 "IMPOSSIBLE"을 출력합니다.

링크: https://www.acmicpc.net/problem/4179

풀이: 두 개의 BFS를 활용한 시간 비교

불의 확산 시간과 지훈이의 이동 시간을 각각 구하여 비교하는 전형적인 두 큐(Queue) 활용 BFS 문제입니다.

1. 불(Fire)의 이동 시간 미리 구하기: 불은 지훈이의 이동 경로와 무관하게 정해진 대로 확산합니다. 따라서 불의 위치를 모두 큐(qF)에 넣고 먼저 BFS 탐색을 진행하여, 미로의 각 칸에 불이 도달하는 최소 시간(fire 배열)을 모두 계산해 둡니다. 불이 도달하지 않는 곳은 안전한 탐색을 위해 Integer.MAX_VALUE로 초기화합니다.
2. 지훈이(J)의 탈출 경로 탐색: 지훈이의 시작 위치를 큐(qP)에 넣고 두 번째 BFS 탐색을 진행합니다.
   • 탈출 조건: 큐에서 꺼낸 지훈이의 현재 위치가 미로의 가장자리(행이 0이거나 R-1, 열이 0이거나 C-1)라면 즉시 탈출에 성공한 것입니다. 방문 배열에 기록된 시간을 출력하고 프로그램을 종료합니다.
   • 이동 조건: 지훈이가 다음 칸으로 이동하려면 다음 조건을 모두 만족해야 합니다.
     1. 맵의 범위를 벗어나지 않아야 합니다.
     2. 벽(#)이 아니어야 합니다.
     3. 불이 도달하는 시간(fire[ny][nx])이 지훈이가 도달할 시간(visited[node.y][node.x] + 1)보다 커야 합니다. (즉, 불보다 먼저 도착해야 함)
     4. 아직 방문하지 않은 칸(visited[ny][nx] == 0)이어야 합니다.
3. 예외 처리: 지훈이의 BFS 탐색이 큐가 빌 때까지 끝났는데도 가장자리에 도달하지 못했다면, 탈출 경로가 불에 막히거나 벽에 갇힌 것이므로 "IMPOSSIBLE"을 출력합니다.

코드

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

public class Main {
    // 상하좌우 이동을 위한 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int r = Integer.parseInt(st.nextToken());
       int c = Integer.parseInt(st.nextToken());

       Queue<Node> qP = new LinkedList<>(); // 지훈이의 이동 큐
       int[][] visited = new int[r][c];     // 지훈이의 방문 시간 기록

       Queue<Node> qF = new LinkedList<>(); // 불의 확산 큐
       int[][] fire = new int[r][c];        // 불이 도달하는 시간 기록

       char[][] a = new char[r][c];
       for (int i = 0; i < r; i++) {
          String s = br.readLine();
          for (int j = 0; j < c; j++) {
             a[i][j] = s.charAt(j);
             
             // 불이 영원히 닿지 않는 곳을 위해 초기값을 무한대로 설정
             fire[i][j] = Integer.MAX_VALUE;
             
             if (a[i][j] == 'J') {
                qP.add(new Node(i, j));
                visited[i][j] = 1; // 시간 계산 편의를 위해 1부터 시작
             } else if (a[i][j] == 'F') {
                qF.add(new Node(i, j));
                fire[i][j] = 1;
             }
          }
       }

       // 1. 불의 확산 시간을 먼저 모두 계산 (BFS)
       while (!qF.isEmpty()) {
          Node node = qF.poll();
          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];
             
             if (ny < 0 || nx < 0 || ny >= r || nx >= c)
                continue;
             // 벽이거나 이미 불이 더 일찍 번진 곳이라면 무시
             if (a[ny][nx] == '#' || fire[ny][nx] != Integer.MAX_VALUE)
                continue;
                
             qF.add(new Node(ny, nx));
             fire[ny][nx] = fire[node.y][node.x] + 1;
          }
       }

       // 2. 지훈이의 이동 경로 탐색 (BFS)
       while (!qP.isEmpty()) {
          Node node = qP.poll();
          
          // 현재 위치가 미로의 가장자리라면 탈출 성공
          if (node.y == 0 || node.x == 0 || node.y == r - 1 || node.x == c - 1) {
             bw.write(visited[node.y][node.x] + "");
             bw.flush();
             return;
          }

          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];
             
             if (ny < 0 || nx < 0 || ny >= r || nx >= c)
                continue;
                
             // 벽이거나, 불이 번지는 시간과 같거나 빠르거나, 이미 방문한 곳이라면 무시
             if (a[ny][nx] == '#' || fire[ny][nx] <= visited[node.y][node.x] + 1 || visited[ny][nx] != 0)
                continue;
                
             qP.add(new Node(ny, nx));
             visited[ny][nx] = visited[node.y][node.x] + 1;
          }
       }

       // 큐가 빌 때까지 가장자리에 도달하지 못했다면 탈출 실패
       bw.write("IMPOSSIBLE");

       bw.flush();
       bw.close();
       br.close();
    }

    static class Node {
       int y, x;

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

알고리즘 분류

그래프 탐색, 너비 우선 탐색 (BFS)