[백준] 4179: 불! (Java)

불!

백준 4179 Gold IV BFS

⏱️ 읽기 시간: 약 6분

📑 목차

• 1. 문제 분석
• 2. 접근법
• 3. 풀이 (Java)
• 4. 예제 트레이스
• 5. 복잡도 분석
• 6. 클린 코드

문제 분석

• R×C 미로에서 지훈이(J)가 불(F)보다 먼저 가장자리에 도달해야 탈출 성공
• 지훈이와 불 모두 매 분마다 상하좌우로 1칸 이동 (벽 통과 불가)
• 불은 여러 개일 수 있고, 동시에 네 방향으로 확산
• 가장자리에 접한 빈 칸에 도달하면 다음 분에 탈출 가능
• 제약: 1 ≤ R, C ≤ 1000 → O(R·C) 풀이 필요

접근법

듀얼 BFS — 두 번의 BFS로 문제를 분리한다:

1단계: 불 BFS

• 모든 불의 초기 위치를 큐에 넣고 BFS 실행
• fireTime[r][c] = 해당 칸에 불이 도착하는 시간
• 불이 도달하지 못하는 칸은 ∞로 유지

2단계: 지훈 BFS

• 지훈이의 초기 위치에서 BFS 실행
• 이동 조건: 지훈 도착 시간 < fireTime[nr][nc] (불보다 먼저 도착해야 함)
• 가장자리 칸에 도달하면 dist + 1 출력 (가장자리에서 밖으로 나가는 1분)

핵심 포인트: 불과 지훈이가 동시에 같은 칸에 도착하면 지훈이는 그 칸을 지나갈 수 없다. 그래서 < (엄격한 부등호)를 사용한다.

풀이 (Java)

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

public class Main {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        char[][] grid = new char[R][C];
        int jr = -1, jc = -1;
        Queue<int[]> fireQ = new LinkedList<>();
        int[][] fireTime = new int[R][C];
        for (int[] row : fireTime) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 0; i < R; i++) {
            grid[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 'J') { jr = i; jc = j; }
                if (grid[i][j] == 'F') {
                    fireQ.add(new int[]{i, j});
                    fireTime[i][j] = 0;
                }
            }
        }

        // 1) 불 BFS — 각 칸에 불이 도착하는 시간 계산
        while (!fireQ.isEmpty()) {
            int[] cur = fireQ.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d], nc = cur[1] + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] == '#') continue;
                if (fireTime[nr][nc] <= fireTime[cur[0]][cur[1]] + 1) continue;
                fireTime[nr][nc] = fireTime[cur[0]][cur[1]] + 1;
                fireQ.add(new int[]{nr, nc});
            }
        }

        // 2) 지훈 BFS — 불보다 먼저 도착 가능한 칸만 이동
        int[][] dist = new int[R][C];
        for (int[] row : dist) Arrays.fill(row, -1);
        dist[jr][jc] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{jr, jc});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            // 가장자리에 도달하면 탈출 (다음 분에 밖으로)
            if (r == 0 || r == R - 1 || c == 0 || c == C - 1) {
                System.out.println(dist[r][c] + 1);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
                // 불보다 먼저 도착해야 함 (동시 도착 불가)
                if (dist[r][c] + 1 >= fireTime[nr][nc]) continue;
                dist[nr][nc] = dist[r][c] + 1;
                q.add(new int[]{nr, nc});
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}

예제 트레이스

입력:
4 4
####
#JF#
#..#
#..#

[1] 불 BFS — fireTime 계산:
     col: 0  1  2  3
row 0:  ∞  ∞  ∞  ∞   (#벽이라 전파 안됨)
row 1:  ∞  ∞  0  ∞   (F 위치 = 시간 0)
row 2:  ∞  2  1  ∞   (F→아래 1분, →왼쪽 2분)
row 3:  ∞  3  2  ∞

[2] 지훈 BFS — dist 계산:
t=0: (1,1) 출발. 가장자리 아님.
t=1: (2,1) 이동. dist=1 < fireTime=2 ✓. 가장자리 아님.
t=2: (3,1) 이동. dist=2 < fireTime=3 ✓.
     (3,1)은 가장자리! → 탈출 시간 = 2 + 1 = 3 ✅

시간 복잡도

O(R·C)

공간 복잡도

O(R·C)

클린 코드 — Java

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

public class Main {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        char[][] grid = new char[R][C];
        int jr = -1, jc = -1;
        Queue<int[]> fireQ = new LinkedList<>();
        int[][] fireTime = new int[R][C];
        for (int[] row : fireTime) Arrays.fill(row, Integer.MAX_VALUE);
        for (int i = 0; i < R; i++) {
            grid[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 'J') { jr = i; jc = j; }
                if (grid[i][j] == 'F') { fireQ.add(new int[]{i, j}); fireTime[i][j] = 0; }
            }
        }
        while (!fireQ.isEmpty()) {
            int[] cur = fireQ.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d], nc = cur[1] + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] == '#' || fireTime[nr][nc] <= fireTime[cur[0]][cur[1]] + 1) continue;
                fireTime[nr][nc] = fireTime[cur[0]][cur[1]] + 1;
                fireQ.add(new int[]{nr, nc});
            }
        }
        int[][] dist = new int[R][C];
        for (int[] row : dist) Arrays.fill(row, -1);
        dist[jr][jc] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{jr, jc});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            if (r == 0 || r == R - 1 || c == 0 || c == C - 1) {
                System.out.println(dist[r][c] + 1);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
                if (dist[r][c] + 1 >= fireTime[nr][nc]) continue;
                dist[nr][nc] = dist[r][c] + 1;
                q.add(new int[]{nr, nc});
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}