[백준 4179/C++] 불!

1. 문제

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

4179번: 불!

---

2. 문제풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)
#define X first
#define Y second

using namespace std;

int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int Fdist[1005][1005];
int Jdist[1005][1005];
string board[1005];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	queue<pair<int, int>> Q1;
	queue<pair<int, int>> Q2;

	for (int i = 0; i < n; i++) {
		fill(Fdist[i], Fdist[i] + m, -1);
		fill(Jdist[i], Jdist[i] + m, -1);
	}
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'F') {
				Q1.push({ i,j });
				Fdist[i][j] = 0;
			}
			if (board[i][j] == 'J') {
				Q2.push({ i,j });
				Jdist[i][j] = 0;
			}
		}
	}
	while (!Q1.empty()) {
		auto cur = Q1.front(); Q1.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nx][ny] == '#' || Fdist[nx][ny] >= 0) continue;
			Fdist[nx][ny] = Fdist[cur.X][cur.Y] + 1;
			Q1.push({ nx,ny });
		}
	}
	while (!Q2.empty()) {
		auto cur = Q2.front(); Q2.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
				cout << Jdist[cur.X][cur.Y] + 1;
				return 0;
			}
			if (board[nx][ny] == '#' || Jdist[nx][ny] >= 0) continue;
			if (Fdist[nx][ny] != -1 && Jdist[cur.X][cur.Y] + 1 >= Fdist[nx][ny]) continue;
			Jdist[nx][ny] = Jdist[cur.X][cur.Y] + 1;
			Q2.push({ nx,ny });
		}
	}
	cout << "IMPOSSIBLE";
}

J

---

2. 문제 평가 및 해설

바킹독님의 알고리즘 강의를 듣고 있어서, 문제 풀이 방법은 금방 생각이 났다.

하지만, 맞왜틀의 저주에 걸려서 2일을 소모한 문제이다..

일단, 문제 풀이는 다음과 같다.

1. 먼저 불이 각 지점 별로 도착하는 시간을 구해야 한다. 이 때, BFS로 불에 대한 시간 맵을 만들어야 한다. 방문한 노드이거나 벽(#)이면 continue를 해준다. 범위가 넘어서는 녀석들도 continue를 해주어야 한다.

2. 지훈이가 탈출하는 최단 시간을 구해야 한다. 이 때, 불이 도달한 시간보다 지훈이가 도달한 시간이 더 오래 걸린다면, continue를 해주어야 한다. 불이 먼저 도달했다는 것은 이동할 수 없다는 것이다. 그리고 위와 마찬가지로, 방문한 노드이거나 벽(#)이면 continue를 해준다. 

3. 지훈이가 탈출하는 최단 시간 BFS에서, 만약 범위에서 넘어선다면, 탈출을 했다는 뜻이므로 값을 출력해준다. 종료해준다.

4. 만약 지훈이의 BFS에서 main 문이 종료가 되지 않았다면, 탈출을 못했다는 것을 의미한다. 따라서 'IMPOSSIBLE'을 출력해준다.

나와 같은 경우, 어처구니 없는 실수를 했는데,  map[cur.X][cur.Y]로 접근해야하는데, map[cur.Y][cur.X]로 접근했다. 또 이실수 코드가 문제에 있는 예제 case를 통과하여서, 오류를 찾는데 어마어마하게 오래걸렸다.. 문제풀이나 논리가 틀린 것이 아니라, "아니 맞는데 왜 틀렸지?"를 계속 외쳤다 ㅠㅠ

반례 case는 다음과 같다.

4 4
####
#JF#
#..#
#..F

answer : IMPOSSIBLE

 

이제 바킹독님의 BFS 관련 문제가 마무리가 되어간다. 마무리가 되는대로, BFS 문제와 관련된 유형을 정리해야겠다.