[백준 5427번] - 불(C++)

5427번: 불

[문제 설명]

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력

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

예제 출력

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

---

[문제 풀이]

마치 게임을 만드는것과 같은 문제였다.

이동 할 수 있는 공안을 moveX, moveY라는 벡터에 미리 저장해뒀다.

또한, Queue와 BFS를 이용하여 문제를 풀었다.

불과 사람 모두 1초에 동서남북으로 이동 할 수 있다.

불은 1초에 동서남북 모두로 퍼지고, 사람은 그 중 한 곳으로만 이동 할 수 있다.

불과 사람 모두 이동 할 수 있는 곳을 Queue에 넣어주었는데,

Queue에 들어가있는 값이 사람인지 불인지 확인해야 하기에 구조체를 하나 만들었다.

 

한가지 조심해야 할 점은 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다 라는 점이다.

위와 같은 조건에 의해 Queue에 불이 이동할 수 있는 위치를 먼저 넣어주면 된다.

 

사람이 공간의 끝 변(x==0 || y==0 || x == w-1 || y == h-1)에 도달하게 되었다는것은 성공적으로 출구에 도착했다는 것이므로 출구에서 나가는 시간 1초를 더해줘서 return하면 된다.

Queue가 empty가 될때까지 도달하지 못했다면 출구가 이미 다 막혀서 도망칠 수 없다는 것이므로 IMPOSSIBLE을 출력해주면 되겠다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

코드

#include <bits/stdc++.h>

using namespace std;

vector<int> moveX = {-1,1,0,0}; // left, right, up, down
vector<int> moveY = {0,0,-1,1}; // left, right, up, down

struct Info{

    enum Types{
        NONE = 0,
        PERSON =1,
        FIRE = 2,
    };

    int xpos =0;
    int ypos =0;
    Types type = NONE;
    int count = 0;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int w,h;
        cin >> w >> h;
        Info cur_Info;
        vector<Info> fire_Info;
        vector<vector<char>> map(h,vector<char>(w,0));

        for(int i = 0; i < h; i++)
        {
            for(int j =0; j < w; j++)
            {
                cin >> map[i][j];
                if(map[i][j] == '@')
                {
                    cur_Info.type = Info::Types::PERSON;
                    cur_Info.count = 0;
                    cur_Info.xpos = j;
                    cur_Info.ypos = i;
                }
                if(map[i][j] == '*')
                {
                    Info temp;
                    temp.type = Info::Types::FIRE;
                    temp.count = 0;
                    temp.xpos = j;
                    temp.ypos = i;
                    fire_Info.push_back(temp);
                }
            }
        }
        bool isFind = false;
        queue<Info> q;
        for(auto& iter : fire_Info) {q.push(iter);}
        q.push(cur_Info);
        while(!q.empty())
        {
            Info front = q.front();
            if(front.type == Info::Types::PERSON &&(front.xpos == 0 || front.ypos == 0 || front.xpos == w-1 || front.ypos == h-1))
            {
                cout << front.count + 1 << "\n";
                isFind = true;
                break;
            }
            q.pop();

            for(int i = 0; i < 4; i++)
            {
                int dx = front.xpos + moveX[i];
                int dy = front.ypos + moveY[i];

                if(dx >= 0 && dy >= 0 && dx < w && dy < h && map[dy][dx] == '.')
                {
                    Info temp;
                    if(front.type == Info::Types::PERSON)
                    {
                        map[dy][dx] = '@';
                    }
                    else
                    {
                        map[dy][dx] = '*';
                    }

                    temp.type = front.type;
                    temp.xpos = dx;
                    temp.ypos = dy;
                    temp.count = front.count +1;
                    q.push(temp);
                }
            }
        }
        if(isFind == false)
        {
            cout << "IMPOSSIBLE" << "\n";
        }
        queue<Info> emptyQueue;
        q = emptyQueue;
        cur_Info = {};
        fire_Info.clear();
        map.clear();
    }
}