[백준 5427] - 불(C++)[골드4]

📕문제

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

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

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

📗입력

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

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

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

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

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

📗출력

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

 

🔎문제 해석

우선 문제를 읽어보면 bfs 알고리즘을 사용해야 한다는 느낌을 받으셔야 합니다.
상하좌우 이동, 가장 빠르게 탈출 -> BFS 
건물을 탈출한다는 뜻은 주어진 배열 밖으로 벗어난다는 뜻입니다.(이거 때매 좀 헷갈림)

 

💡문제 풀이

• 우선 기본적으로 상근이와 불을 계속 이동해서 푸는 문제입니다.
  • 불은 벽 빼고는 모두 이동할 수 있으며, 이동하는 즉시 불이 번집니다.
  • 상근이는 벽과 불빼고 모두 이동가능합니다.
    • 하지만 여기서 중요한점은 불이 "붙을 예정"이라는 말이 중요한 점입니다.
      불이 붙은 곳은 당연히 가지 못합니다. 하지만 불이 붙을 예정..? 말이 조금 애매합니다.
• 우선 이동하는데 걸리는 시간은 1초입니다.
  • 상근이는 불이 붙을 예정인 지역을 이동하지 못합니다.
    • 따라서 우리는 불의 이동을 먼저 시행한 뒤, 상진이의 이동을 시행해야 합니다.
      • 만약 상진이를 먼저 이동시킨뒤다면, 불이 붙을 지역임에도 불구하고, 상진이가 이동해버리기 때문에
        오류가 발생합니다.

🖥️코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int t, n, m;
vector<vector<char> > graph;
bool check = false;
int answ = 0;
int x[4] = {0, 0, 1, -1};
int y[4] = {-1, 1, 0, 0};
void funct(queue<pair<int,int> >people,queue<pair<int,int> >fire);
int main()
{
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n >> m;
        graph.assign(m, vector<char>(n, 0));
        queue<pair<int, int> > people;
        queue<pair<int, int> > fire;
        check = false;
        answ = 0;
        for (int j = 0; j < m; j++)
        {
            for (int k = 0; k < n; k++)
            {
                cin >> graph[j][k];
                if (graph[j][k] == '*'){ // 불
                    fire.push(make_pair(j, k));
                }
                else if (graph[j][k] == '@'){ // 시작 위치.
                    people.push(make_pair(j, k));
                }
            }
        }
        funct(people,fire);
        if (check == true){ // 탈출 가능.
            cout << answ << endl;
        }
        else{ //탈출 불가능.
            cout << "IMPOSSIBLE" << endl;
        }
    }
}
void funct(queue<pair<int,int> >people,queue<pair<int,int> >fire)
{
    bool flag = false;
    int time = 0;
    while (!people.empty())
    {
        time++;
        int cnt = 0, size = fire.size();
        while (size != cnt) // 불이동
        {
            int row = fire.front().first,col = fire.front().second;
            fire.pop();
            for (int d = 0; d < 4; d++){
                int temprow = row + x[d];
                int tempcol = col + y[d];

                if (temprow < 0 || temprow >= m || tempcol < 0 || tempcol >= n){
                    continue;
                }
                if (graph[temprow][tempcol] != '.'){
                    continue;
                }
                graph[temprow][tempcol] = '*';
                fire.push(make_pair(temprow, tempcol));
            }
            cnt++;
        }
        int psize = people.size(), cnt2 = 0;
        while (psize != cnt2) //상근이 이동
        {
            int px = people.front().first,py = people.front().second;
            people.pop();
            for (int i = 0; i < 4; i++)
            { 
                int px2 = px + x[i], py2 = py + y[i];
                if (px2 < 0 || py2 < 0 || px2 >= m || py2 >= n){ // 배열 밖으로 나갔으면 탈출임
                    check = true;
                    answ = time;
                    return;
                }
                if (graph[px2][py2] == '.'){
                    people.push(make_pair(px2, py2));
                    graph[px2][py2] = '@';
                }
                else
                    continue;
            }
            cnt2++;
        }
    }
}

 

😃느낀 점

• 다른 bfs문제들과 조금 색달랐다고 느꼈고, 거기에서 살짝 헤맸다.
• 다른 사람들의 코드를 보니 나의 문제점이 보여서 이러한 점을 참고해서 다음 코드부터는 조금 더 깔끔하고, 가독성 있게 짜야겠다고 
  느꼈습니다!
  • 시간 차이가 너무 심하더라고요,,,