백준 4179 불! c++(bfs)

문제 출처 : https://www.acmicpc.net/problem/4179

4179번: 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

bfs의 동작 방식을 제대로 이해하고 있어야 하는 문제이다.

bfs를 돌리는 경우는 지훈이의 이동, 불의 이동이 있다.

또한, 불은 여러 군데에서 시작할 수 있기 때문에(F가 여러 개 주어질 수 있다)

[i][j]칸에 지훈이와 불이 몇 초 만에 이동했는지를 정확히 파악해야 한다.

 

우선 시간에 따른 불의 이동 경로를 저장할 fire_map[][]의 모든 칸에 불이 도달하는 시간을 저장한다.

그 후 지훈이가 이동할 graph[][]에서 이동했을 때, 불보다 빨리 도착할 수 있는지, 벽이 아닌지,

이미 방문했는지(이미 방문했다면 다시 방문할 필요가 없다)를 파악하고 이동한다.

 

 

반례

10 10
F........F
F........F
F........F
F........F
F...J....F
F........F
F........F
F........F
F........F
F........F

답 impossible

 

10 10
#........#
#........#
#........#
#........#
#...J....#
#........#
#........#
#........#
#........#
FFFFFFFFFF

 

답5

 

3 3
F.F
.J.
F.F

 

답impossible

 

코드

#include <iostream>
#include <queue>
using namespace std;
int R, C;
char graph[1000][1000];
bool visited[1000][1000];
int fire_map[1000][1000];
vector<pair<int, int>> fire;
int groupCnt = 0;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

void make_fireMap() {
	vector<queue<pair<int, int>>> fireQ(fire.size());

	for (int i = 0; i < fire.size(); i++) {
		fireQ[i].push({ fire[i].first,fire[i].second });
	}

	for (int f = 0; f < fireQ.size(); f++) {
		while(!fireQ[f].empty()) {
			int cur_fireR = fireQ[f].front().first;
			int cur_fireC = fireQ[f].front().second;
			fireQ[f].pop();

			for (int i = 0; i < 4; i++) {
				int	next_fireR = cur_fireR + dir[i][0];
				int	next_fireC = cur_fireC + dir[i][1];
				if (next_fireR >= 0 && next_fireR < R && next_fireC >= 0 && next_fireC < C && graph[next_fireR][next_fireC] != '#') {
					if (fire_map[cur_fireR][cur_fireC] + 1 < fire_map[next_fireR][next_fireC]) {
						fireQ[f].push({ next_fireR,next_fireC });
						fire_map[next_fireR][next_fireC] = fire_map[cur_fireR][cur_fireC] + 1;
					}
				}
				
			}
		}
	}
}
void move(int startR, int startC) {
	queue<pair<pair<int,int>,int>> startQ;
	
	startQ.push({ { startR,startC },0 });
	

	while (!startQ.empty()) {

		int cur_startR = startQ.front().first.first;
		int cur_startC = startQ.front().first.second;
		int cnt = startQ.front().second;

		if (cur_startR == 0 || cur_startR == R-1 || cur_startC == 0 || cur_startC == C-1) {//나갔을 때
			cout << cnt + 1;
			return;
		}
		startQ.pop();
		for (int i = 0; i < 4; i++) {
			int next_startR = cur_startR + dir[i][0];
			int next_startC = cur_startC + dir[i][1];
			if (next_startR >= 0 && next_startR < R&&next_startC >= 0 && next_startC < C) {
				if (fire_map[next_startR][next_startC] > cnt + 1 && graph[next_startR][next_startC] == '.') {
					if (!visited[next_startR][next_startC]) {
						startQ.push({ { next_startR,next_startC },cnt + 1 });
						visited[next_startR][next_startC] = true;
					}
				}
			}

		}
	}


	cout << "IMPOSSIBLE";
	return ;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C;
	
	pair<int,int>start;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			char ch;
			cin >> ch;
			if (ch == 'F') {
				fire.push_back({ i,j });
				graph[i][j] = 'F';
				fire_map[i][j] = 0;
				
			}
			else if (ch == 'J') {
				start = { i,j };
				graph[i][j] = '.';
				fire_map[i][j] = 987654321;
			}
			else {
				graph[i][j] = ch;
				fire_map[i][j] = 987654321;
			}
		}
	}
	make_fireMap();
	move(start.first, start.second);
	return 0;
}