불!

백준 4179번: 불!

아이디어

간단한 bfs문제다. 불이 번지는 미로랑 지훈이가 움직이는 미로를 따로 만든다. 불을 먼저 다 번지게 만들고, 지훈이가 그 불보다 빠르게 갈 수 있는 곳을 찾아서 큐에 집어넣는다.

코드

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int r, c;
    queue<pair<int, int>> jq;
    queue<pair<int, int>> fq;
    
    //input
    cin >> r >> c;
    for (int row = 0; row < r; row++) {
        string input;
        cin >> input;
        for (int col = 0; col < c; col++) {
            if (input[col] == '#') {
                maze_j[row][col] = -1;
                maze_f[row][col] = -1;
            }
            else if (input[col] == 'J') {
                maze_j[row][col] = 1;
                jq.push({row, col});
            }
            else if (input[col] == 'F') {
                maze_f[row][col] = 1;
                fq.push({row, col});
            }
        }
    }
    
    // bfs(fire)
    while (!fq.empty()) {
        int sr = fq.front().first;
        int sc = fq.front().second;
        fq.pop();
        
        for (int i = 0; i < 4; i++) {
            int nr = sr + dy[i];
            int nc = sc + dx[i];
            if (nr >= r || nc >= c || nr < 0 || nc < 0) {
                continue;
            }
            else if (maze_f[nr][nc] != 0) {
                continue;
            }
            else {
                maze_f[nr][nc] = maze_f[sr][sc] + 1;
                fq.push({nr, nc});
            }
        }
    }
    
    // bfs(jihun)
    bool imp = true;
    while (!jq.empty()) {
        int sr = jq.front().first;
        int sc = jq.front().second;
        if (sr == 0 || sr == r - 1 || sc == 0 || sc == c - 1) {
            cout << maze_j[sr][sc] << '\n';
            imp = false;
            break;
        } 
        jq.pop();
        
        for (int i = 0; i < 4; i++) {
            int nr = sr + dy[i];
            int nc = sc + dx[i];
            if (nr >= r || nc >= c || nr < 0 || nc < 0) {
                continue;
            }
            else if (maze_j[nr][nc] != 0) {
                continue;
            }
            // check fire
            else if (maze_f[nr][nc] <= maze_j[sr][sc] + 1 && maze_f[nr][nc] != 0) {
                continue;
            }
            else {
                maze_j[nr][nc] = maze_j[sr][sc] + 1;
                jq.push({nr, nc});
            }
        }
    }
    
    if (imp) {
        cout << "IMPOSSIBLE\n";
    }
    
    return 0;
}

여담

불이 하나도 없는 경우를 조심하자. 지도에 있는 숫자가 다 0이 되어버려서 지훈이가 움직일 수 없다..