[ C++ ] #5427 불 (골드 IV)

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

문제

---

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

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

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

입력

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

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

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

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

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

출력

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

풀이

---

BFS 문제이다.

오래걸리긴 했지만 혼자 풀어낸 문제여서 매우 뿌듯하다. 하지만 코드가 깔끔하거나 효율적인지는 모르겠다.

사용한 자료구조는 다음과같다.

• char map[1000][1000] : 입력으로 받은 지도를 그대로 저장
• int check[1000][1000] : 상근이 방문했는지 체크하는 배열
• int F_check[1000][1000] : 불이 퍼졌는지 체크하는 배열
• queue<pair<int, int>> fire : 한 라운드에서 퍼져나가야하는 불들의 위치 큐
• queue<pair<int, int>> man : 한 라운드에서 이동시킨 상근이의 위치 큐

사용한 함수들은 다음과같다.

• int is_people() : 상근이가 불에 탔을 때 다른 상근이가 있는지 확인하는 함수
• void removeElement(pair<int, int> target) : 불에 탄 상근이를 큐에서 제거하는 함수

이제 알고리즘을 보자. 테스트코드가 n번 들어오기 때문에 그 과정은 생략하고 한번의 테스트 코드가 어떻게 동작하는지 정리해보겠다.

1. 배열들 초기화 후 지도 입력받기
2. flag가 0이 될 때까지 아래 과정 반복 (반복횟수가 즉 움직인 횟수)
   1. man의 사이즈만큼 반복
      1. man의 front의 위치에서 이동시킬 위치를 man에 push
      2. 해당 위치가 check되어있지 않을 시 push
   2. flag가 0이면 break
   3. man의 사이즈가 0이면, 즉 상근이 갈 곳이 없다면 IMPOSSIBLE
   4. fire의 사이즈만큼 반복
      1. fire의 front의 위치에서 불이 퍼질 위치를 fire에 push
      2. 상근이를 잡으면
         1. 상근이를 man 큐에서 지우고 map에서 불로 바꾸기
         2. 더이상 남은 사람이 없다면 IMPOSSIBLE 하고 flag=0
      3. 상근이를 잡지 않으면 그냥 불로 태우기

스파게티 코드같다고 생각했는데 나름 정리하고 보니까 괜찮은거같기도하다. 흠

Code

#include <iostream>
#include <queue>

using namespace std;

int w, h, n;
char map[1000][1000];
int check[1000][1000];
int F_check[1000][1000];
queue<pair<int, int>> fire;
queue<pair<int, int>> man;

int is_people()
{
    for (int x = 0; x < h; x++)
    {
        for (int y = 0; y < w; y++)
        {
            if(map[x][y]=='@'){ //사람 있음
                return 1;
            }
        }
    }
    return 0; // 사람 없음
}

void removeElement(pair<int, int> target) {//man에서 잡한녀석 제거
    queue<pair<int, int>> tempQueue;

    // 큐를 탐색하면서 특정 요소를 찾고 삭제
    while (!man.empty()) {
        pair<int, int> current = man.front();
        man.pop();

        if ((current.first != target.first ) || (current.second != target.second )) {
            tempQueue.push(current);
        }
    }

    // 원래 큐에 다시 복사
    while (!tempQueue.empty()) {
        man.push(tempQueue.front());
        tempQueue.pop();
    }
}

int main(){
    int manX, manY; // 상근의 위치
    cin >> n;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, -1, 0, 1};

    for (int i = 0; i < n; i++){
        // 반복 전에 배열들을 초기화 
        for (int i = 0; i < 1000; ++i) {
            for (int j = 0; j < 1000; ++j) {
                map[i][j] = 0;
                check[i][j] = 0;
                F_check[i][j] = 0;
            }
        }

        cin >> w >> h;
        while(!fire.empty()){  fire.pop();  }
        while(!man.empty()){  man.pop();  }
        int move = 0;
        
        // 지도 입력받기
        for (int x = 0; x < h; x++) {
            for (int y = 0; y < w; y++) {
                char c;
                cin >> c;
                map[x][y]=c;
                if (c == '*'){
                    fire.push(make_pair(x, y));
                    F_check[x][y]=1;
                }
                else if (c == '@'){
                    man.push(make_pair(x, y));
                    check[x][y]=1;
                }
            }           
        }
        
        // 상근 움직이기
        int flag = 1;
        while (flag){      
            int man_num = man.size();
            move++;
            while (man_num--){

                int temp_x = man.front().first;
                int temp_y = man.front().second;
                man.pop();
            
                if (temp_x == 0 || temp_y == 0 || temp_y == w - 1 || temp_x == h - 1){ // 테두리라면
                    cout << move << '\\n';
                    flag=0;
                    break;
                }
                
                for (int j = 0; j < 4; j++){

                    int xx = temp_x + dx[j];
                    int yy = temp_y + dy[j];

                    if (xx < 0 || xx >= h || yy < 0 || yy >= w){ // 범위밖이라면
                        continue;
                    }
                    if (map[xx][yy] == '#'||map[xx][yy] == '*'){ // 벽이나 불이라면
                        continue;
                    }
                    if(check[xx][yy]==0){
                        man.push(make_pair(xx, yy));
                        map[temp_x][temp_y] = '.';
                        map[xx][yy] = '@';
                        check[xx][yy]=1;
                    }
                }
            }
            if(flag==0){
                break;
            }
            if(man.size()==0){ //상근 갈 곳이 없다면
                cout << "IMPOSSIBLE\\n";
                break;
            }

            // 불 퍼지기
            int fire_num = fire.size();
            while(fire_num--){
                int temp_x = fire.front().first;
                int temp_y = fire.front().second;
                fire.pop();

                for (int j = 0; j < 4; j++){

                    int xx = temp_x + dx[j];
                    int yy = temp_y + dy[j];

                    if (xx < 0 || xx >= h || yy < 0 || yy >= w){ // 범위 밖이라면
                        continue;
                    }
                    if (map[xx][yy] == '#'){ //벽이라면
                        continue;
                    }
                    else if (map[xx][yy] == '@') {  //사람을 잡으면
                        if(F_check[xx][yy]==0){
                            if(map[xx][yy]='@'){
                                removeElement(make_pair(xx,yy));
                            }
                            fire.push(make_pair(xx, yy));
                            map[xx][yy] = '*';
                            F_check[xx][yy];
                        }
                        if(is_people()==0){ //다른사람이 없다면

                            cout << "IMPOSSIBLE\\n";
                            flag = 0;
                            break;

                        }
                    
                    }else{
                        if(F_check[xx][yy]==0){
                            fire.push(make_pair(xx, yy));
                            map[xx][yy] = '*';
                            F_check[xx][yy]=1;
                        }
                    }                  
                }
                if(flag==0) break;
            }
        }

    }
    return 0;
}