[백준/C++] 5427번 불

문제: www.acmicpc.net/problem/5427

5427번: 불

 

 

문제풀이

 

BFS를 이용해 최단거리를 구하는 문제이다.

 

불과 상근이의 시작점을 큐에 넣어 BFS 하면 상근이는 먼저 붙어있는 불을 피해 이동할 수 있게 된다.

이때 상근이를 큐의 마지막에 넣어야 불과 상근이가 같은 장소로 동시에 이동하는 일이 없다.

 

 

코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
string board[1000];
int dist[1000][1000];

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

    int t;
    cin>>t;

    while(t--){
        int w,h,tmp1,tmp2;
        cin>>w>>h;

        for(int i=0; i<h; i++)
            fill(dist[i], dist[i]+w, -1);

        bool flag = true;
        queue<tuple<int,int,char>> q;
        for(int i=0; i<h; i++){
            cin>>board[i];
            for(int j=0; j<w; j++){
                if(board[i][j] == '*'){ //불 시작점
                    q.push(make_tuple(i,j,'f'));
                    dist[i][j] = 0;
                }

                if(board[i][j] == '@'){ //상근이 시작점
                    tmp1=i;
                    tmp2=j;
                }
            }
        }

        q.push(make_tuple(tmp1,tmp2,'s')); //상근이는 마지막에 큐에 넣는다.
        dist[tmp1][tmp2] = 0;

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

            for(int dir=0; dir<4; dir++){
                int nx = get<0>(cur) + dx[dir];
                int ny = get<1>(cur) + dy[dir];
                char nc = get<2>(cur);

                if(nx<0||nx>=h||ny<0||ny>=w){ //범위를 벗어남
                    if(nc == 's'){ //범위를 벗어난 것이 상근이면 탈출 성공
                        cout<<dist[get<0>(cur)][get<1>(cur)] + 1<<"\n";
                        flag = false;
                        break;
                    }
                    else continue; //불이면 continue
                }
                if(dist[nx][ny] >= 0 || board[nx][ny] != '.') continue;

                dist[nx][ny] = dist[get<0>(cur)][get<1>(cur)] + 1;
                q.push(make_tuple(nx,ny,nc));
            }

            if(!flag) break; 
            //상근이가 탈출을 성공했다면 큐에 남아있는 상근이가 다른 값을 출력할 수 있으므로 while문을 break
        }

        if(flag){
            cout<<"IMPOSSIBLE"<<"\n";
        }
        
        while(!q.empty()) q.pop();
    }

    return 0;
}

 

 

결과