5427번: 불 (BOJ C/C++)

5427번: 불

사용 언어: C++

문제

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

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

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

입력

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

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

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

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

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

출력

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

 

풀이

불과 상근이가 움직일 보드인 visF, visS를 따로 설정하고 visF의 BFS를 따로 돌리고 visS의 BFS를 돌리면서 visF와 비교하면 풀 수 있다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int TC, w, h;
int board[1002][1002];
int visF[1002][1002]; //불
int visS[1002][1002]; //상근

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>TC;
	while(TC--)
	{
		queue<pair<int, int>> QF = {}, QS = {}; //불, 상근
		bool check = false;
		cin >> w >> h;
		for(int i=0; i<h; i++)
		{
			fill(visF[i], visF[i]+w, 0);
			fill(visS[i], visS[i]+w, 0);
		}
		for(int i=0; i<h; i++)
			for(int j=0; j<w; j++)
			{
				char c;
				cin>>c;
				if(c=='#')
					board[i][j] = -1;
				else
				{
					if(c=='@')
					{
						QS.push({i,j});
						visS[i][j]=1;
					}
					else if(c=='*')
					{
						QF.push({i,j});
						visF[i][j]=1;
					}
					board[i][j]=0;
				}
			}
		while(!QF.empty())
		{
			auto cur = QF.front(); QF.pop();
			for(int i=0; i<4; i++)
			{
				int nx = cur.X + dx[i];
				int ny = cur.Y + dy[i];
				if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
				if(board[nx][ny] == -1) continue;
				if(visF[nx][ny]) continue; //visF >= 1 -> continue;
				visF[nx][ny] = visF[cur.X][cur.Y] + 1;
				QF.push({nx,ny});
			}
		}
		while(!QS.empty() && !check)
		{
			auto cur = QS.front(); QS.pop();
			for(int i=0; i<4; i++)
			{
				int nx = cur.X + dx[i];
				int ny = cur.Y + dy[i];
				if(nx<0 || nx>=h || ny<0 || ny>=w) //상근이 탈출
				{
					cout << visS[cur.X][cur.Y] << '\n';
					check = true;
					break;
				}
				if(board[nx][ny] == -1) continue;
				if(visS[nx][ny]) continue;
				if(visF[nx][ny] != 0 && visF[nx][ny] <= visS[cur.X][cur.Y] + 1) continue;
				visS[nx][ny] = visS[cur.X][cur.Y] + 1;
				QS.push({nx,ny});
			}
		}
		if(!check) cout<<"IMPOSSIBLE"<<'\n';
	}
	return 0;
}