[C++] BOJ 5427 / BFS (불 따로 사람 따로)

문제 분석

https://www.acmicpc.net/problem/5427

한 쪽으로 영향을 미치는(불이 사람에게) 문제이다. 불이 사람보다 먼저 탐색하여 지나간 길을 사람이 지나갈 수 없다.

서로에게 영향을 미치는 문제는 백트래킹을 사용해야 하며, 해당 문제는 추후에 다루도록 하겠다.

 

해결 방법

BFS를 불 먼저 시간(거리)를 계산하여 기록하고, 사람을 후에 계산하면서 불 보다 늦게 지나가는(거리가 더 먼) 지점은 벽 처럼 큐에 넣지 않도록 continue하는 조건을 추가하면 된다.

 

코드

#include <iostream>
#include <queue>
#include <utility>
#include <string>

using namespace std;
#define X first
#define Y second
int board[1001][1001];
int dist1[1001][1001];
int dist2[1001][1001];
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, m, t;
    char c;
    cin >> t;
    while(t--) {
        queue<pair<int,int>> q1;
        queue<pair<int,int>> q2;
        int exit=0;
        int ans;
        cin >> m >> n;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                cin >> c;
                if(c == '#') {
                    board[i][j] = -1;
                }
                else if(c == '*') {
                    q1.push({i,j});
                    dist1[i][j] = 1;
                }else if(c == '@') {
                    q2.push({i,j});
                    dist2[i][j] = 1;
                }
            }
        }
        while(!q1.empty()) {
            pair<int,int> cur = q1.front();
            q1.pop();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx<0||nx>=n||ny<0||ny>=m) continue;
                if(dist1[nx][ny] != 0 || board[nx][ny] == -1) continue;
                q1.push({nx,ny});
                dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
            }
        }
        while(!q2.empty() && exit != 1) {
            pair<int,int> cur = q2.front();
            q2.pop();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(nx<0||nx>=n||ny<0||ny>=m) {
                    exit = 1;
                    ans = dist2[cur.X][cur.Y];
                    break;
                }
                if(dist2[nx][ny] != 0 || board[nx][ny] == -1) continue;
                if(dist1[nx][ny] != 0 && dist2[cur.X][cur.Y] + 1 >= dist1[nx][ny]) continue;
                dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
                q2.push({nx,ny});
                
            }
        }
        for(int i=0;i<n;i++) {
            fill(board[i],board[i] + m, 0);
            fill(dist1[i],dist1[i] + m, 0);
            fill(dist2[i],dist2[i] + m, 0);
        }
        if(exit) cout << ans << "\n";
        else    cout << "IMPOSSIBLE\n";
    }
}

   

풀이 복습

코드는 약 30분 정도 걸려서 작성했지만, 제출하면 계속 "틀렸습니다"가 떠서 반례를 찾아서 넣는 과정에서 오래걸렸다.

하지만 문제는 반례가 아니었는데, 테스트 케이스에 따라 while문을 돌리는데 제대로 초기화를 안해서 다음 케이스에 영향을 끼친 것이 문제였다.

나의 경우에는 사용한 queue를 초기화 하지 않아서 이전 케이스에서 break를 통해 빠져나오면 다음 케이스에 영향을 끼쳤다.

테스트 케이스가 여러개인 경우에는 항상 변수 초기화에 신경써야겠다.