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

백준 문제 풀이: 4179 [불!]

---

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

문제 설명:

불이 퍼지는 미로에서 지훈이가 탈출할 수 있는 최소 시간을 계산하는 문제입니다. 미로는 벽('#'), 빈 칸('.'), 지훈이의 위치('J'), 불의 위치('F')로 구성되어 있으며, 불은 매 초마다 4방향으로 퍼집니다. 지훈이는 불보다 먼저 가장자리에 도달해야 탈출할 수 있습니다.

---

문제 해결 코드

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

int arr[1001][1001];  // 미로 상태
int visited[1001][1001]; // 방문 여부
int t[1001][1001];   // 불이 퍼지는 시간
int J[1001][1001];   // 지훈이 이동 경로
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

void Fbfs(int a, int b) { // 불 BFS
    q.push({a, b});
    t[a][b] = 0;

    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();

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

            if (kx < 0 || ky < 0 || kx >= r || ky >= c) continue;
            if (arr[kx][ky] == 1 || visited[kx][ky] == 1) continue;

            visited[kx][ky] = 1;
            t[kx][ky] = t[nx][ny] + 1;
            q.push({kx, ky});
        }
    }
}

void Jbfs(int a, int b) { // 지훈 BFS
    q.push({a, b});
    J[a][b] = 0;

    while (!q.empty()) {
        int nx = q.front().first;
        int ny = q.front().second;
        q.pop();

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

            if (kx < 0 || ky < 0 || kx >= r || ky >= c) continue;
            if (arr[kx][ky] == 1 || visited[kx][ky] == 1) continue;
            if (t[kx][ky] <= J[nx][ny] + 1 && t[kx][ky] > 0) continue;

            visited[kx][ky] = 1;
            J[kx][ky] = J[nx][ny] + 1;
            q.push({kx, ky});
        }
    }
}

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

    cin >> r >> c;
    char ch;
    int Jindexi, Jindexj;

    // 미로 입력
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> ch;
            if (ch == '#') arr[i][j] = 1;       // 벽
            else if (ch == '.') arr[i][j] = 2;  // 빈 칸
            else if (ch == 'J') {               // 지훈
                arr[i][j] = 3;
                Jindexi = i;
                Jindexj = j;
            } else if (ch == 'F') {             // 불
                arr[i][j] = 4;
            }
        }
    }

    // 불 BFS 실행
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (arr[i][j] == 4) {
                Fbfs(i, j);
                memset(visited, 0, sizeof(visited));
            }
        }
    }

    // 지훈 BFS 실행
    Jbfs(Jindexi, Jindexj);

    // 최소 시간 계산
    int minTime = 1000001;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (i != 0 && j != 0 && i != r - 1 && j != c - 1) continue;
            if (arr[i][j] == 2 && J[i][j]) {
                minTime = min(minTime, J[i][j]);
            } else if (arr[i][j] == 3) {
                minTime = 0;
            }
        }
    }

    if (minTime == 1000001) {
        cout << "IMPOSSIBLE";
    } else {
        cout << minTime + 1;
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 불의 확산 시간을 먼저 계산한 뒤, 지훈이가 탈출 가능한 경로를 BFS로 탐색합니다. 지훈이의 이동 시간과 불의 확산 시간을 비교하여 탈출 가능 여부를 판별합니다.
• 구현 세부사항:
  • Fbfs: 불의 확산 시간을 계산하는 BFS
  • Jbfs: 지훈이의 이동 시간을 계산하는 BFS
• 시간 복잡도 분석: O(rc)
  • 행과 열의 개수가 r, c일 때, BFS 탐색은 각각 O(rc)입니다.

---

결과

지훈이가 불을 피하며 탈출 가능한 최소 시간을 정확히 계산합니다. BFS를 사용하여 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!