BOJ_5427 C++

BOJ 5427 불

문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

풀이과정

첫 접근은 3가지에 집중했다.

• 출구까지 불의 최단경로
• 출구까지 상근이의 최단경로
• 상근이의 탈출 가능 여부 점검

각각의 조건을 BFS로 찾아내어 불의 최단경로가 상근이의 최단경로보다 짧거나 혹은 상근이가 건물밖으로 나갈수 없는 경우일 때 IMPOSSIBLE을 출력하게 하고 그 외의 경우 상근이의 탈출 최단 경로를 출력하도록 코딩해보았다.

그에 대한 코드는 다음과 같다.

오답코드

//BOJ 5427
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;


char building[1000][1000]; //[H][W]
int vis[1000][1000];
int vis_fire[1000][1000];
queue<pair<int,int>> q; //{H,W}

int _dx[4] = {0,0,-1,1};
int _dy[4] = {-1,1,0,0};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    //테스트케이스 T (최대 100)
    int T;
    cin >> T;

    for(int test=0; test<T; test++){
        int MIN_human = 100000001;
        int MIN_fire = 100000001;
        bool escape = false;

        int _h, _w;
        cin >> _w >> _h;

        // 빌딩정보 입력.
        for(int height=0; height<_h; height++){
            string temp;
            cin >> temp;

            for(int b_s=0; b_s<temp.size(); b_s++){
                building[height][b_s] = temp[b_s];
            }
        }

        //BFS시작 .. 최단거리 구하기 및 최단거리 이동정보 저장...?!
        for(int i=0; i<_h; i++){ // 상근이 위치 기준 BFS시작...!
            for(int j=0; j<_w; j++){
                if(building[i][j] != '@') continue; // 상근이의 위치 찾기

                q.push({i,j});
                vis[i][j] = 1;

                while(!q.empty()){
                    pair<int,int> cur = q.front();
                    q.pop();

                    for(int k=0; k<4; k++){
                        int _x = cur.first + _dx[k]; //_h
                        int _y = cur.second + _dy[k]; // _w

                        if(building[_x][_y] != '.') continue;
                        if(vis[_x][_y]) continue;
                        if(_x<0 || _y<0 || _x>=_h || _y>=_w) continue;

                        q.push({_x,_y});
                        vis[_x][_y] = vis[cur.first][cur.second] + 1;

                        if(_x==0 || _y==0 || _x==_h-1 || _y==_w-1){
                            MIN_human = min(MIN_human, vis[_x][_y]);
                            escape = true;
                        }
                    }
                }

                for(int i_1=0; i_1<_h; i_1++){
                    for(int j_1=0; j_1<_w; j_1++){
                        vis[i_1][j_1] = 0;
                    }
                } // 상근이 기준 BFS이후 방문기록 초기화
            }
        }

        for(int i=0; i<_h; i++){ // 불 위치 기준 BFS시작...!
            for(int j=0; j<_w; j++){
                if(building[i][j] != '*') continue; // 불 위치 찾기...! 만약 불이 2개 이상이라면...?

                q.push({i,j});
                vis_fire[i][j] = 1;

                while(!q.empty()){
                    pair<int,int> cur = q.front();
                    q.pop();

                    for(int k=0; k<4; k++){
                        int _x = cur.first + _dx[k]; //_h
                        int _y = cur.second + _dy[k]; // _w

                        if(building[_x][_y] == '#') continue;
                        if(vis_fire[_x][_y]) continue;
                        if(_x<0 || _y<0 || _x>=_h || _y>=_w) continue;

                        q.push({_x,_y});
                        vis_fire[_x][_y] = vis_fire[cur.first][cur.second] + 1;

                        if(_x==0 || _y==0 || _x==_h-1 || _y==_w-1){
                            MIN_fire = min(MIN_fire, vis_fire[_x][_y]);
                        }
                    }
                }

                for(int i_1=0; i_1<_h; i_1++){
                    for(int j_1=0; j_1<_w; j_1++){
                        vis_fire[i_1][j_1] = 0;
                    }
                } // 불 하나당 BFS이후 vis_fire 초기화
            }
        }               
    
        if(!escape || MIN_fire <= MIN_human){
            cout << "IMPOSSIBLE\n";
        }
        else{
            cout << MIN_human << "\n";
        }
    }//최단거리를 확인한 후 최단거리 정보 저장.

    return 0;
}

여기서 확인할 수 있는 점은 상당이 여러번 BFS과정을 거친다는 것이다.

상근이의 경우 1명으로 문제 조건에 주어졌지만 불의 경우는 여러개가 존재할 수 있다. 나의 경우 불을 하나씩 찾을 때 마다 BFS를 각각 진행해주어 여러개의 불 중 건물탈출구를 막는 최단경로를 저장하는 식으로 접근했다.

이러한 풀이과정으로 진행하니 시간초과가 발생하였다.
아마 BFS가 여러번 반복될 수 있어서 그렇다고 생각한다.

이후 불의 이동을 우선적으로 BFS한 이후 상근이를 움직이는 방법을 채택했지만 25%에서 오류가 발생한다...?
2023.01.19