[BOJ/C++] 4179번 불! : BFS 시작점 종류 여러개

문제 설명

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

문제 해결

해당 문제는 시작점의 종류가 여러개 이므로 BFS를 불과 지훈이 총 2번을 한다.

visJ 와 visF 행렬을 통해서 각 불과 지훈이가 해당 칸에 도달하는 초를 기록한다.

불 BFS를 먼저 진행하고 지훈이의 BFS를 진행한다. 이 때 같은 칸에 불이 지훈이 보다 먼저 도달하거나, 같이 도달 할 경우 지훈이는 해당 경로를 가지 못하므로 조건문을 설정한다.!!

그리고 지훈이의 BFS는 입력한 행렬 사이즈를 벗어나면 끝나므로 (탈출) 조건문 안에 Q의 front x,y 인덱스일때 칸의 값을 출력한다.

하지만 while문이 끝나도록 종료되지 않을 경우 탈출하지 못한 경우이므로 IMPOSSIBLE를 출력한다.

코드

#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int visJ[1002][1002]; //지훈이 방문
int visF[1002][1002]; // 불 방문

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int R, C;
	cin >> R >> C;
	pair<int, int> J;
	pair<int, int>F;
	string* arr = new string[R];
	for (int i = 0; i < R; i++) {
		fill(visJ[i], visJ[i] + C, -1);
		fill(visF[i], visF[i] + C, -1);
	}
	queue < pair<int, int>> q1; //지훈이 큐
	queue<pair<int, int>>q2; // 불 큐
	for (int i = 0; i < R; i++)
	{
		cin >> arr[i];
		for (int j = 0; j < C; j++) {
			if (arr[i][j] == 'J') {
				J = { i,j };
				visJ[i][j] = 0;
				q1.push(J);
			}
			else if (arr[i][j] == 'F') {
				F = { i,j };
				visF[i][j] = 0;
				q2.push(F);
			}
		}
	}
	while (!q2.empty()) { // 불 BFS
		auto curF = q2.front();
		q2.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nxF = curF.X + dx[dir];
			int nyF = curF.Y + dy[dir];
			if (nxF < 0 || nxF >= R || nyF < 0 || nyF >= C) continue;
			if (visF[nxF][nyF] >= 0 ||arr[nxF][nyF] == '#' ) continue;
			visF[nxF][nyF] = visF[curF.X][curF.Y] + 1;
			q2.push({ nxF,nyF });
		}
	}
	while (!q1.empty()) { // 지훈이 BFS
		auto curJ = q1.front();
		q1.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nxJ = curJ.X + dx[dir];
			int nyJ = curJ.Y + dy[dir];
			if (nxJ < 0 || nxJ >= R || nyJ < 0 || nyJ >= C) {
				cout << visJ[curJ.X][curJ.Y] + 1;
				return 0;
			}
			if (visJ[nxJ][nyJ]>=0 || arr[nxJ][nyJ] == '#') continue;
			if (visF[nxJ][nyJ] != -1 && visF[nxJ][nyJ] <= visJ[curJ.X][curJ.Y] + 1)continue; // 불이 먼저 도달했거나, 불과 같이 도달할 경우
			visJ[nxJ][nyJ] = visJ[curJ.X][curJ.Y] + 1;
			q1.push({ nxJ,nyJ });
		}
	}
	cout << "IMPOSSIBLE";
}