[C++] 백준/Gold/4179. 불！

불 ! (백준 4179번)

문제 개요

• 문제 설명:
  미로에서 지훈이(J)가 불(F)로부터 탈출하는 최소 시간을 구하는 문제
  • 미로는 벽(#), 빈 공간(.), 불(F), 지훈이(J)로 구성됨
  • 불은 매 초마다 상하좌우 인접한 빈 공간으로 확산
  • 매 초마다 상하좌우로 한 칸 이동 가능하며, 벽이나 불이 있는 곳으로 이동 불가
  • 미로 밖으로 나가면 탈출 성공
  • 탈출이 불가능하면 "IMPOSSIBLE" 출력
• 핵심 포인트:
  • 불의 확산과 J의 이동을 시간 단위로 동기화하며 시뮬레이션 해야 함
  • BFS를 이용하여 J의 이동과 불의 확산을 순차적으로 처리

접근 방법

1. 불 확산과 지훈이 이동을 동시에 처리하는 BFS

• 불의 현재 위치를 set에 저장해 매 시간마다 인접한 빈 공간으로 확산
• J의 위치를 queue에 저장해 BFS 탐색 진행
• J의 이동 시간이 바뀔 때마다 불 확산 함수를 호출하여 상태 갱신

2. 상태 표현 및 유효성 검사

• 미로 상태를 다음과 같이 표현
  • 0: 벽 (#)
  • 1: 빈 공간 (.)
  • 2: 불 (F)
• J의 방문 여부를 2차원 visited 배열로 관리
• 좌표 유효성 검사 함수 IsValidIndex 활용하여 미로 범위 확인

3. 탈출 조건

• J가 미로 경계 밖으로 이동하는 순간 탈출 성공
• BFS가 종료될 때까지 탈출하지 못하면 "IMPOSSIBLE" 출력

전체 코드

#include <bits/stdc++.h>
using namespace std;

int offset[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
int r, c;

bool IsValidIndex(int x, int y) {
    return x >= 0 && x < c && y >= 0 && y < r;
}

void FireSpread(vector<vector<int>>& grid, set<pair<int,int>>& fires) {
    set<pair<int,int>> nextFire;
    for (const auto& [y, x] : fires) {
        for (int i = 0; i < 4; i++) {
            int xx = x + offset[i][0];
            int yy = y + offset[i][1];
            if (IsValidIndex(xx, yy) && grid[yy][xx] == 1)
                nextFire.insert({yy, xx});
        }
    }
    for (const auto& [y, x] : nextFire)
        grid[y][x] = 2;
    swap(fires, nextFire);
}

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

    cin >> r >> c;
    vector<vector<int>> grid(r, vector<int>(c));
    vector<vector<bool>> visited(r, vector<bool>(c, false));
    set<pair<int,int>> fires;
    pair<int,int> start;

    for (int i = 0; i < r; i++) {
        string str; cin >> str;
        for (int j = 0; j < c; j++) {
            if (str[j] == '#') grid[i][j] = 0;
            else if (str[j] == 'F') {
                fires.insert({i, j});
                grid[i][j] = 2;
            }
            else grid[i][j] = 1;

            if (str[j] == 'J') start = {i, j};
        }
    }

    queue<tuple<int,int,int>> bfs; // {시간, x, y}
    visited[start.first][start.second] = true;
    bfs.push({1, start.second, start.first});
    int time = 0;

    while (!bfs.empty()) {
        auto [currentTime, x, y] = bfs.front();
        bfs.pop();

        if (currentTime != time) {
            FireSpread(grid, fires);
            time++;
        }

        for (int i = 0; i < 4; i++) {
            int xx = x + offset[i][0];
            int yy = y + offset[i][1];

            if (!IsValidIndex(xx, yy)) {
                cout << time;
                return 0;
            }

            if (grid[yy][xx] == 1 && !visited[yy][xx]) {
                visited[yy][xx] = true;
                bfs.push({currentTime + 1, xx, yy});
            }
        }
    }

    cout << "IMPOSSIBLE";
}