백준 5427번 [불](C++) -yes6686- 티스토리

백준 문제 풀이: 5427 (불)

---

문제 링크: https://www.acmicpc.net/problem/5427

문제 설명:

2차원 빌딩 내부에서 상근이는 불이 번지기 전에 빌딩을 탈출해야 합니다. 상근이는 한 칸씩 상하좌우로 이동할 수 있고, 불도 동일하게 상하좌우로 퍼져 나갑니다. 벽('#')은 통과할 수 없으며, 상근이가 경계 밖으로 나가면 탈출 성공입니다. 불이 먼저 도착하는 칸은 상근이가 갈 수 없습니다. 탈출에 필요한 최소 시간(초)을 출력하며, 불가능할 경우 IMPOSSIBLE을 출력합니다.

---

문제 해결 코드

// 5427번: 불
// 두 번의 BFS (불 → 상근이), 불보다 먼저 도착하는 경로만 이동 가능

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

char arr[1001][1001];
int fire[1001][1001];        // 불 도착 시간
int visited[1001][1001];     // 방문 체크
int h, w;
int minAns = 1000001;

queue<pair<pair<int, int>, int>> q;

// k == 2: 불 BFS, k == 1: 상근이 BFS
void bfs(int x, int y, int k) {
    q.push({ {x, y}, 1 });
    visited[x][y] = 1;

    while (!q.empty()) {
        int kx = q.front().first.first;
        int ky = q.front().first.second;
        int cnt = q.front().second;
        q.pop();

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

            if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                if (k == 1) { // 상근이 탈출
                    minAns = min(minAns, cnt + 1);
                }
                continue;
            }

            if (arr[nx][ny] == '#' || visited[nx][ny]) continue;
            visited[nx][ny] = 1;

            if (k == 1) {
                if (fire[nx][ny] == 0 || fire[nx][ny] > cnt + 1) {
                    q.push({ {nx, ny}, cnt + 1 });
                }
            } else { // 불
                fire[nx][ny] = fire[kx][ky] + 1;
                q.push({ {nx, ny}, cnt + 1 });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        cin >> w >> h;
        int sx, sy;
        int firex = -1, firey = -1;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> arr[i][j];
                if (arr[i][j] == '@') {
                    sx = i;
                    sy = j;
                } else if (arr[i][j] == '*') {
                    q.push({ {i, j}, 1 });
                    fire[i][j] = 1;
                    firex = i;
                    firey = j;
                    visited[i][j] = 1;
                }
            }
        }

        // 불 먼저 확산
        if (firex != -1) bfs(firex, firey, 2);

        // 상근이 이동
        memset(visited, 0, sizeof(visited));
        bfs(sx, sy, 1);

        if (minAns == 1000001) {
            cout << "IMPOSSIBLE" << '\n';
        } else {
            cout << minAns - 1 << '\n';
        }

        // 초기화
        minAns = 1000001;
        while (!q.empty()) q.pop();
        memset(arr, 0, sizeof(arr));
        memset(fire, 0, sizeof(fire));
        memset(visited, 0, sizeof(visited));
    }
}

---

코드 설명

• 핵심 알고리즘: BFS 2회 (불 → 상근이)
• 불 확산: 각 칸에 도착하는 시간을 기록하여 상근이의 이동 제한
• 상근이 이동: 도착 시간 < 불 도착 시간일 경우만 이동
• 탈출 조건: 경계를 벗어나는 순간 탈출 성공

---

결과

상근이가 탈출할 수 있는 최소 시간(초)을 출력합니다. 탈출 불가 시 IMPOSSIBLE 출력.

예시 입력:
2
4 3
#### #*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######

예시 출력:
2
5

문제에 대한 다른 의견이나 개선 아이디어가 있다면 댓글로 공유해주세요!