백준 4179 : 불!

www.acmicpc.net/problem/4179

4179번: 불!

상하좌우로 움직일 수 있을 때 최단거리를 찾는 전형적인 BFS문제이다. 다만 사람뿐만 아니라 불도 움직인다는 점을 고려해야 한다. 문제에서 불이 먼저 움직이는지 지훈이가 먼저 움직이는지는 알려주지 않는다. 

 

그럼 지훈이가 먼저 움직인다고 가정해보자. 지훈이가 움직인 후 만약 불이 지훈이가 움직인 위치로 번진다면 지훈이는 죽어버리므로 정답이 될 수 없다. 물론 지훈이가 죽어버려도 큐 안에 들어있는 살아있는 지훈이가 다른 길로 가는 경우를 꺼내와 다시 길을 찾아도 된다. 하지만 비효율적이다. 매번 불이 움직일 때마다 해당 위치에 지훈이가 있는지 살펴봐야 한다. 어차피 정답이 될 수 없다면 아에 배제해버릴수 없을까?

 

자 그럼 불이 먼저 움직인다고 가정해보자. 불이 먼저 자유롭게 움직이고 나서 지훈이를 움직이면 지훈이는 불이 있는 곳으로 가면 죽어버리므로 그냥 다른 길로 가버리면 된다. 이 경우 지훈이의 위치를 체크할 필요도 없고 단순히 불과 지훈이의 방문체크만 해주면 그만이다.

 

사실 둘이 움직이는 순서는 결과에 영향을 미치지 않는다. 이렇게 생각해보자. 만약 지훈이도 a라는 지점으로 가고 불도 a라는 지점으로 번진다면, 불이 먼저 번지든, 지훈이가 먼저 움직이든 순서는 상관없이 지훈이는 죽는다. 불이 먼저 움직인다고 했지만 이는 로직을 단순화 하기 위한 한가지 방법일 뿐이다.

 

그럼 아마 지금쯤 이런 생각이 들 것이다.

문제에 있는 예제에는 지훈이랑 불이랑 처음부터 바로 옆에 붙어있는데 그럼 불이 먼저 움직이면 지훈이 즉사하는거 아니냐?

 

아니다. 불이 지훈이 위치로 번지는 동안 지훈이는 이미 다른 곳으로 가버린다고 생각하면 되는 것이다. 만약 지훈이의 사방이 모두 벽이나 불 그리고 자신이 이미 방문한 지점으로 둘러싸여있다면 그 때 지훈이는 죽는다. 

 

코드는 아래와 같다. 입력값을 받으면서 visited 배열 값을 바꿔주고 BFS를 도는 동안은 문자는 신경쓰지 않고 visited 배열만 확인했는데, 그 이유는 벽이나 불에 막혀서 못가는 것이나, 최단거리로 가기 위해서 방문한 지점을 다시 방문하지 않는 것이나 결국 못간다는 점에서 같기 때문에 원인이 무엇인지는 확인할 필요가 없기 때문이다.

 

따라서 불을 담는 큐 fq, 지훈이를 담는 큐 q를 따로 선언해두고 지훈이가 움직이기 전에 먼저 불들을 움직여준 다음 지훈이를 이동시켜줬다. 지훈이가 움직이는 BFS안에 불이 움직이는 BFS가 들어있는 형태이다.

 

#include <iostream>
#include <queue>
#include <string>
#include <tuple>

using namespace std;

int R, C;
bool visited[1000][1000];
queue<tuple<int, int, int>> fq;
queue<tuple<int, int, int>> q;

void bfs() {
	int x, y, fx, fy, cnt, fcnt, nx, ny, min_val = 1e9;
	int dx[] = { -1,1,0,0 };
	int dy[] = { 0,0,-1,1 };

	while (!q.empty()) {
		tie(x, y, cnt) = q.front();
		q.pop();
		
		if (x == 0 || y == 0 || x == C - 1 || y == R - 1) {
			min_val = cnt;
			break;
		}
	
		while (!fq.empty()) {
			tie(fx, fy, fcnt) = fq.front(); 
			if (fcnt != cnt) break;
			fq.pop();

			for (int k = 0; k < 4; k++) {
				nx = fx + dx[k]; ny = fy + dy[k];
				if (nx < 0 || nx >= C || ny < 0 || ny >= R || visited[ny][nx]) continue;
				fq.emplace(nx, ny, fcnt + 1);
				visited[ny][nx] = 1;
			}
		}
		
		for (int k = 0; k < 4; k++) {
			nx = x + dx[k]; ny = y + dy[k];
			if (nx < 0 || nx >= C || ny < 0 || ny >= R || visited[ny][nx]) continue;
			q.emplace(nx, ny, cnt + 1);
			visited[ny][nx] = 1;
		}
	}

	if (min_val != 1e9) cout << min_val;
	else cout << "IMPOSSIBLE";
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string tmp;
	cin >> R >> C;
	for (int j = 0; j < R; j++) {
		cin >> tmp;
		for (int i = 0; i < C; i++) {
			if (tmp[i] == 'J') {
				q.emplace(i, j, 1);
				visited[j][i] = 1;
			}
			else if (tmp[i] == 'F') {
				fq.emplace(i, j, 1);
				visited[j][i] = 1;
			}
			else if (tmp[i] == '#') {
				visited[j][i] = 1;
			}
		}
	}
	bfs();
	return 0;
}

메모리 3128kb

시간 36ms