[Algorithm/C++17] 백준 5427 불

문제

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

5427번: 불

풀이 방법

미로탈출 문제와 유사하지만 '불' 개념이 추가되어 시간이 지남에 따라 이동할 수 없는 지역이 추가되는 것이 차이점이다. 상근이가 바깥으로 나가는건 BFS로 풀 수 있고 마찬가지로 불도 상하좌우 한칸씩 움직이기 때문에 BFS로 갱신해주면 된다. 다만 새로운 노드 탐색을 할때 원래는 현재 방문 노드에서 인접한 노드들만을 탐색한다. 하지만 이 문제에서는 불이 전체적으로 퍼지기 때문에 이 탐색 과정을 큐의 크기만큼 반복한다. (즉 모든 노드의 인접 노드를 탐색한다)

따라서 반복문 한번마다 현재 큐에 있는 불과 상근이 노드가 서로 확장하는 형태가 된다. 예를 들면 두 번째 테스트 케이스에서 다음과 같은 형태가 된다.

// result: 0
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######

// result: 1
###.###
#*#.#*#
#*...*#
#..@..#
#.@@@.#
#######

// result: 2
###.###
#*#.#*#
#**@**#
#*@@@*#
#@@@@@#
#######

// result: 3
###.###
#*#@#*#
#*****#
#**@**#
#*@@@*#
#######

// result: 4
###@###
#*#*#*#
#*****#
#*****#
#**@**#
#######

// result: 5
// 탈출 성공
   @
###*###
#*#*#*#
#*****#
#*****#
#*****#
#######

 코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int dy[] ={-1,0,0,1};
int dx[] ={0,-1,1,0};
int main() {
	int t, w, h;
	char c;
	scanf("%d", &t);
	while(t--)
	{
        queue<pair<int,int>> sanggun;
        queue<pair<int,int>> fire;
		scanf("%d %d", &w, &h);
		vector<vector<char>> v(h+1, vector<char>(w+1, '.'));
        vector<vector<bool>> visited(h+1, vector<bool>(w+1, false));
		for(int i=0; i<h; i++)
		{
			for(int j=0; j<w; j++)
			{
				scanf(" %1c", &c);
				v[i][j]=c;
                if(c=='@')
                {
                    visited[i][j] = true;
                    sanggun.push({i,j});
                }
                else if(c=='*')
                {
                    fire.push({i,j});
                }
			}
		}
        bool success = false;
        int result = 0;
        while(!sanggun.empty())
        {
            result++;
            size_t qsize = sanggun.size();
            for(int i=0; i<qsize; i++)
            {
                int y = sanggun.front().first;
                int x = sanggun.front().second;
                sanggun.pop();
                if(v[y][x] == '*') continue;
                for(int j=0; j<4; j++)
                {
                    int ny = y + dy[j];
                    int nx = x + dx[j];
                    if(ny<0 || ny>=h || nx<0 || nx>=w)
                    {
                        success = true;
                        break;
                    }
                    if(v[ny][nx] == '.' && !visited[ny][nx])
                    {
                        visited[ny][nx] = true;
                        sanggun.push({ny,nx});
                    }
                }
            }
            if(success) break;
            qsize = fire.size();
            for(int i=0; i<qsize; i++)
            {
                int y = fire.front().first;
                int x = fire.front().second;
                fire.pop();
                for(int j=0; j<4; j++)
                {
                    int ny = y+dy[j];
                    int nx = x+dx[j];
                    if(ny<0 || ny>=h || nx<0 ||nx>=w) continue;
                    if(v[ny][nx] == '.')
                    {
                        v[ny][nx] = '*';
                        fire.push({ny,nx});
                    }
                }
            }
        }
        if(success)
            printf("%d\n", result);
        else
            printf("IMPOSSIBLE\n");
	}
	return 0;
}

고찰

왜 큐의 크기 만큼 반복해줘야하는지 몰랐지만 직접 출력해보니 이해가 됐던 문제이다. 비슷한 문제는 https://www.acmicpc.net/problem/3055 이다.

3055번: 탈출