[BOJ / C++] 불 (BFS)

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

 

1. 코드

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

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

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

    int n;
    cin >> n;
    while (n--) {
        int c, r;
        cin >> c >> r;

        queue<pair<int, int>> fireQ;
        queue<pair<int, int>> personQ;
        
        vector<vector<int>> fDist(r, vector<int>(c, -1));
        vector<vector<int>> pDist(r, vector<int>(c, -1));
        
        vector<vector<char>> board(r, vector<char>(c, ' '));
        for (int i = 0; i < r; i++) {
            string str;
            cin >> str;
            for (int j = 0; j < c; j++) {
                board[i][j] = str[j];
                
                if (board[i][j] == '*') {
                    fireQ.push({i, j});
                    fDist[i][j] = 0;
                }
                else if (board[i][j] == '@') {
                    personQ.push({i, j});
                    pDist[i][j] = 0;
                }
            }
        }

        // fire bfs
        while (!fireQ.empty()) {
            auto cur = fireQ.front(); fireQ.pop();
            int x = cur.first;
            int y = cur.second;
            
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if (board[nx][ny] == '#' || fDist[nx][ny] >= 0) continue;
                
                fireQ.push({nx, ny});
                fDist[nx][ny] = fDist[x][y] + 1;
            }
        }

        // person bfs
        bool escape = false;
        while (!personQ.empty() && !escape) {
            auto cur = personQ.front(); personQ.pop();
            int x = cur.first;
            int y = cur.second;
            
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    cout << pDist[x][y] + 1 << '\n';
                    escape = true;
                    break;
                }
                if (board[nx][ny] == '#' || board[nx][ny] == '*' || pDist[nx][ny] >= 0) continue;
                // 불이 없는 case도 check 해줘야함!
                if (fDist[nx][ny] != -1 && pDist[x][y] + 1 >= fDist[nx][ny]) continue; 

                personQ.push({nx, ny});
                pDist[nx][ny] = pDist[x][y] + 1;
            }
        }
        
        if (!escape) cout << "IMPOSSIBLE" << '\n'; 
    }
}

 

2. 분석

    불의 거리 bfs를 먼저 처리하고, 사람(상근)의 거리 bfs를 체크해주면 된다. 조금 다른 것은 escape 변수를 둬서 보드 범위 바깥으로 나가면 탈출한 것이므로 해당 부분을 처리해주는 것을 신경써주면 된다.

// 불이 아얘 없는 Edge case를 신경쓰지 못한 코드
if (pDist[x][y] + 1 >= fDist[nx][ny]) continue;

// 불이 없는 경우까지 신경쓴 올바른 구현
if (fDist[nx][ny] != -1 && pDist[x][y] + 1 >= fDist[nx][ny]) continue;

 

    처음에 테스트케이스는 맞추는데 제출하면 '틀렸습니다' 판정을 받았는데 이 부분을 한참 찾았다. 첫번째 처럼 코드를 짜게 되면 불이 번진 시간보다 사람이 가는 시간이 더 길면 배제하는 것 같아 맞아 보이지만 불이 아얘 없는 경우를 신경쓰지 못한 것이다. 문제에 직접적으로 불이 없을 수도 있다고 써있지는 않지만 테스트 케이스에 그 힌트가 있었다. 

 

문제의 마지막 케이스에 보면 "IMPOSSIBLE"이라 크게 신경쓰지 않았지만 사람과 벽만 있고, 불이 없는 것을 알 수 있다. 즉, 불이 board에 없을 수 있고, 아래와같은 케이스도 가능한 것이다.

// board
# # #
# @ .
# # #

// fDist
-1  -1  -1
-1  -1  -1
-1  -1  -1

// 불이 아얘 없는 Edge case를 신경쓰지 못한 코드
if (pDist[x][y] + 1 >= fDist[nx][ny]) continue;

// 불이 없는 경우까지 신경쓴 올바른 구현
if (fDist[nx][ny] != -1 && pDist[x][y] + 1 >= fDist[nx][ny]) continue;

 

fDist에 모든 원소가 -1이 되어서 불이 없을 때도 항상 continue에 걸려버리게 된다. 그래서 fDist[nx][ny] != -1 && 로 불이 번진 상태에서 pDist + 1이 fDist에 안될 때만 continue를 해줘야한다.

 

3. 시간복잡도

시간 복잡도는 O(n * r * c)가 된다. 100 * 1000 * 1000 = 10^8이므로 1초 안에 수행 가능하다.