[백준/BOJ] 4179번 불! (C++)

www.acmicpc.net/problem/4179

4179번: 불!

조금 색다른 유형의 BFS 문제 유형이었습니다.

BFS를 두번 진행해야하는데, 먼저 불의 BFS를 진행하여 불의 확산시간을 fvisit 배열에 기록하고, 다음에 지훈 BFS를 진행하여 불의 확산시간과 비교하면서 이동시간을 기록합니다. 지훈이가 특정 위치에 이동하기 위해선 불의 확산이 진행되지 않은 곳이거나, 그 위치에서의 불의 확산 시간과 지훈이의 이동시간을 비교해 불의 확산시간이 더 커야 이동할 수 있습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int r, c;
char map[1001][1001];
int fvisit[1001][1001];
int jvisit[1001][1001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int > > fire, jihoon; 

void jBFS() {
    queue<pair<int, int > > q;
    q.push(jihoon[0]);
    jvisit[jihoon[0].first][jihoon[0].second] = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
                cout << jvisit[x][y] + 1;
                return;
            }
            if(jvisit[nx][ny] != -1 || map[nx][ny] == '#') continue;
            if(fvisit[nx][ny] != -1 && fvisit[nx][ny] <= jvisit[x][y] + 1) continue;
            q.push({ nx, ny });
            jvisit[nx][ny] = jvisit[x][y] + 1;
        }
    }
    
    cout << "IMPOSSIBLE";
}

void fBFS() {
    queue<pair<int, int > > q;
    for(int i = 0; i < fire.size(); i++) {
        q.push(fire[i]);
        fvisit[fire[i].first][fire[i].second] = 0;
    }
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if(fvisit[nx][ny] != -1 || map[nx][ny] == '#') continue;
            q.push({ nx, ny });
            fvisit[nx][ny] = fvisit[x][y] + 1;
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> r >> c;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> map[i][j];
            if(map[i][j] == 'F') fire.push_back({ i, j }); // 불 위치 저장
            else if(map[i][j] == 'J') jihoon.push_back({ i, j }); // 지훈 위치 저장
        }
    }
    
    // 불 BFS
    memset(fvisit, -1, sizeof(fvisit));
    fBFS();
    
    // 지훈 BFS
    memset(jvisit, -1, sizeof(jvisit));
    jBFS();
}