[BFS]백준 4179번 불!

백준 4179번

불!

우선 지훈이가 미로에서 길을 찾는 것은 최단거리를 찾는 것과 동일하기 때문에 BFS로 구현해야 한다는 것을 알 수 있다.

불이 퍼지는 것 또한 편리하게 BFS를 이용하여 구현하였다.

알고리즘은 다음과 같다.

1. 입력을 받는다.
2. 불을 지른다.
3. 지훈이가 현재 위치에서 움직일 수 있는 모든 방향으로 한 칸 움직인다.
4. 2,3을 반복한다.

중요한 것은, 불을 지르고 지훈이 현재 위치’들’ 에서 움직일 수 있는 모든 칸을 움직여봐야 한다는 것이다.

불을 지르는 타이밍과 지훈이 움직이는 타이밍을 제대로 맞춰준다면 가볍게 풀 수 있는 문제이다.

지훈이 움직이는 것보다 불을 먼저 지르는 이유는, 지훈이 먼저 움직이는 경우 불이 퍼진 곳에 지훈이가 있는지, 있다면 불이 질러진 시점보다 앞인지 뒤인지를 따로 확인하는 과정이 매우 번거롭기 때문이다.

우선 불을 질러놓고 지훈이 움직일 수 없는 조건을 설정해준다면 지훈이가 이동할 수 있는 좌표가 담긴 큐가 비는지만 확인해주면 된다.

BFS를 연속해서 돌리는게 아니라 한 칸씩 움직이고 불과 지훈이가 번갈아가며 BFS를 실행해야 한다는 게 조금 어렵게 느껴질 수 있지만, 각자 time queue를 만들고, 자신을 큐에 넣는 좌표의 time 보다 +1 된 시간을 자신의 time으로 가지게 하고 queue의 front가 현재 좌표의 time과 다른 경우 차례를 바꾸게 만들면 된다.

디버깅하는데 시간이 너무 오래 걸렸는데, 나는 불을 지르는 타이밍을 잘못 계산해서 그랬다.

또한, 대부분의 반례가 통과해버려서 더 오류를 찾기 어려웠다.

질문 검색 게시판에서 찾은 반례이다.

정답이 5가 나온다면 불을 지르는 타이밍과 지훈이 움직이는 타이밍은 잘 설정한 것으로 보면 된다.

10 10
#........#
#........#
#........#
#........#
#...J....#
#........#
#........#
#........#
#........#
FFFFFFFFFF

이 문제는 워털루 대학의 프로그래밍 대회에 나왔던 것으로, 반례들이 정리되어 있다.

반례 보기

에서 문제 B 번의 데이터와 정답을 참고하면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
int height, width;
char maze[1001][1001];
int time_jihun[1001][1001]={-1,};
int time_fire[1001][1001]={-1,};
bool visited[1001][1001]={false,};
bool fireVisited[1001][1001]={false,};
pair<int, int> Jihun;
pair<int,int> fire;
int iter_y[4] = {1,0,-1,0};
int iter_x[4] = {0,1,0,-1};
queue<pair<int,int> > firePos;
void printMaze(){
     for(int a=0;a<height;a++){
            for(int b=0;b<width;b++){
                cout << maze[a][b] << " ";
            }
            cout << endl;
        }
        cout << endl;
}
void setFire(){
    //  cout << "setFire!!!\n";
    //  cout << firePos.size() << endl;
    while(!firePos.empty()){
        pair<int,int> cur = firePos.front();
        firePos.pop();
        // cout << cur.first << " " << cur.second << endl;
        for(int i=0;i<4;i++){
            int y = cur.first + iter_y[i];
            int x = cur.second + iter_x[i];

            if((maze[y][x]=='.' || maze[y][x]=='J')&&!fireVisited[y][x]){
                firePos.push(make_pair(y,x));
                fireVisited[y][x] = true;
                maze[y][x] = 'F';
                time_fire[y][x] = time_fire[cur.first][cur.second] + 1;
            }
        }
        if(time_fire[cur.first][cur.second] != time_fire[firePos.front().first][firePos.front().second]){
            return;
            break;
        }
    }
}

int main(){
    cin >> height >> width;

    for(int i=0;i<height;i++){
        string tmp;
        cin >> tmp;
        for(int j=0;j<tmp.size();j++){
            maze[i][j] = tmp[j];
            if(tmp[j]=='J'){
                Jihun.first = i;
                Jihun.second = j;
                time_jihun[i][j] = 1;
                visited[i][j] = true;
            }
            if(tmp[j]=='F'){
                fire.first = i;
                fire.second = j;
                time_fire[i][j] = 1;
                firePos.push(make_pair(i,j));
            }
        }
    }
    queue<pair<int,int> > q;
    q.push(Jihun);

    while(!q.empty()){
        setFire(); 
        while(1){
            pair<int,int> cur = q.front();
            if(cur.first == height-1 || cur.first == 0 || cur.second == 0 || cur.second == width-1){
                cout << time_jihun[cur.first][cur.second] << endl;
                return 0;

            }
            q.pop();
            // printMaze();
                for(int i=0;i<4;i++){
                    int y = cur.first + iter_y[i];
                    int x = cur.second + iter_x[i];

                    if(y >= 0 && x>=0 && y < height && x < width){
                        // cout << y << " " << x << endl;
                        if(maze[y][x]=='.' && !visited[y][x]){
                            // cout << endl << y << " " << x << endl;
                            q.push(make_pair(y,x));
                             maze[y][x] = 'J';
                            visited[y][x] = true;
                            time_jihun[y][x] = time_jihun[cur.first][cur.second] + 1;
                        }
                    }
                }
            if(time_jihun[cur.first][cur.second] != time_jihun[q.front().first][q.front().second]){
                break;
            }
        //    printMaze(); 
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}