BOJ - 5427. 불

문제

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

---

풀이 과정

• 가장 빠른 시간을 구하는 문제이므로 BFS 탐색 방법으로 접근하였다.
• 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다고 문제에서 언급되었기 때문에 먼저 불에 대해 탐색을 하고, 다음에 사람에 대해 탐색을 하면됩니다.
• 불의 시작점(*) 은 어러군데일 수 있으므로 벡터로 받아 벡터에 있는 시작점을 모두 큐에 삽입하며 시작한다.
• • 에서 상하좌우로 탐색을 진행하여 불이 붙을 수 있는 공간이라면 * 로 변환시켜준다.

for(int j=0;j<4;j++){
                int nextY = curY + dy[j];
                int nextX = curX + dx[j];
                if(nextY<0 || nextX<0 || nextY>=h || nextX>=w){
                    continue;
                }
                if(arr[nextY][nextX]=='.'){
                    arr[nextY][nextX]='*';
                    fires.push(make_pair(nextY,nextX));
                }
            }

• 다음은 사람의 이동에 대해 상하좌우로 탐색해줘야한다.
• 만약 벽쪽에 있으면 탈출에 성공한 것이므로 현재까지 이동한 거리를 반환해줍니다.

if(curY==0 || curX==0 || curY==h-1 || curX==w-1){
                    //벽쪽이면 탈출가능
                    return answer;
            }

• 루프 조건에 q.size() 라고 하면 루프안에서 큐를 삽입,삭제하는 과정으로 인해 크기가 일정해지지 않는다 . → 따로 변수를 만들어 미리 큐의 크기를 저장해둬야한다.

int queueSize = q.size();
for(int i=0;i<queueSize;i++){

• 만약 탐색을 다 했는데 탈출을 못했으면 -1을 반환한다.

---

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;
int n;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int w,h; //h-y, w-x
char arr[1001][1001];
bool visit[1001][1001];
int startPointY;
int startPointX;
vector<pair<int,int>> fire;

int bfs(){
    queue<pair<int,int>> q;
    queue<pair<int,int>> fires;
    q.push(make_pair(startPointY,startPointX));

    for(int i=0;i<fire.size();i++){
        fires.push(make_pair(fire[i].first,fire[i].second));
    }
    int answer = 1;
    while(!q.empty()){
        int fireSize = fires.size();
        for(int i=0;i<fireSize;i++){
            int curY = fires.front().first;
            int curX = fires.front().second;
            fires.pop();
            for(int j=0;j<4;j++){
                int nextY = curY + dy[j];
                int nextX = curX + dx[j];
                if(nextY<0 || nextX<0 || nextY>=h || nextX>=w){
                    continue;
                }
                if(arr[nextY][nextX]=='.'){
                    arr[nextY][nextX]='*';
                    fires.push(make_pair(nextY,nextX));
                }
            }
        }
        int queueSize = q.size();
        for(int i=0;i<queueSize;i++){
            //사람 움직이는거
            int curY = q.front().first;
            int curX = q.front().second;
            q.pop();
            if(curY==0 || curX==0 || curY==h-1 || curX==w-1){
                    //벽쪽이면 탈출가능
                    return answer;
            }
            for(int j=0;j<4;j++){
                int nextY = curY+dy[j];
                int nextX = curX+dx[j];

                if(nextY<0 || nextX<0 || nextY>=h || nextX>=w){
                    continue;
                }

                if(visit[nextY][nextX]==false && arr[nextY][nextX]=='.' ){
                    //방문 안함 + 빈공간이어야지 이동가능
                    //방문체크
                    visit[nextY][nextX]=true;
                    //큐 삽입
                    q.push(make_pair(nextY,nextX));

                }

            }
        }

        answer++;
    }
    return -1;

}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        fire.clear(); //큐 초기화
        memset(visit,false,sizeof(visit)); //방문 초기화

        cin>>w>>h;


        for(int j=0;j<h;j++){
            string str;
            cin>>str;
            for(int k=0;k<w;k++){
                arr[j][k]=str[k];
                if(str[k]=='@'){
                    startPointY=j;
                    startPointX=k;
                }else if(str[k]=='*'){
                    fire.push_back(make_pair(j,k));
                }
            }
        }

        int a = bfs();
        if(a==-1){
            cout<<"IMPOSSIBLE"<<'\n';
        }else{
            cout<<a<<'\n';
        }

    }

    return 0;
}