[백준/c++] 4179 - 불!

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

4179번: 불!

---

1) 풀이

분명 예전에 푼 문제인데.. 왜 이렇게 어려운 걸까😂

예전에 한 번 풀고 다시 복습하고 있음에도 어려운 문제들이 너무 많다...

공부엔 끝이 읍다... 후.

 

아무튼, 이 문제 또한 BFS 문제인데

이건 두개의 BFS 탐색을 돌린다고 생각하면 된다.

하나는 1) 불의 이동, 하나는 2) 지훈이의 이동 이렇게 해서!

 

그럼 어떤 것을 먼저 탐색하느냐 가 중요한데,

이 문제에서 불의 이동은 지훈이의 이동에 영향을 받지 않지만

지훈이의 이동은 불의 이동에 영향을 받기 때문에

(불이 확산된칸은 지훈이가 지나가지 못하기 때문!)

불의 이동을 먼저 탐색해주고 그 다음에 지훈이의 이동을 탐색해주면 된다!

 

다른 BFS 문제와 똑같이 탐색할 지점의 좌표를 넣을 queue와

칸을 지나가는 시간을 저장해줄 visit 배열을 두개씩 만들어준다.

(시간은 시작지점으로부터의 거리와 똑같다! 이해가 안 된다면 이전글을 보고 오자)

 

미로에서 J와 F가 입력되면 각각의 queue에 좌표를 집어넣는다.

이것을 시작점으로 하여 BFS 탐색을 시작하기 때문.

 

1. 불의 이동

현재 탐색하는 좌표(cur)의 상하좌우를 살펴보고, 미로의 범위를 벗어나거나 벽(#)이 들어있는 칸이거나 이미 탐색을 했다면 continue를 해주고 아니라면 queue에 좌표를 넣어주면서 불이 지나간 시간 배열의 현재 탐색하고 있는 좌표(cur) 값에 1을 더한 값을 상하좌우 칸에 넣어준다.

 

2. 지훈이의 이동

현재 탐색하는 좌표(cur)의 상하좌우를 살펴보고, 벽(#)이 들어있는 칸이거나 이미 탐색을 했다면 continue를 해주지만

불의 이동과는 다르게 미로의 범위를 벗어난다면 지훈이가 탈출에 성공한 것이므로 지훈이가 지나간 시간 배열의 현재 탐색하는 좌표(cur)의 값에 1을 더한 값을 출력하고 프로그램을 종료한다.

 

또한, 지훈이는 불이 붙은 칸을 지나갈 수 없다! 불의 시간 배열에 현재 탐색하는 상하좌우의 좌표를 넣어 지훈이가 지금 이동하는 시간과 비교해서 지훈이가 지나가는 시간이 불의 이동 시간보다 크거나 같다면 이미 불이 붙거나 지훈이가 지나갈 때 붙는다는 의미이므로 continue 해준다.

 

이 과정에서 유의해야 할 점이 있다.

지훈이가 지나간 시간과 불이 지나간 시간을 저장하는 배열은 모두 -1로 초기화하는데(시작점은 0으로 시작)

지훈이가 지나갈 자리에 불의 시간이 -1이 아닌지, 즉 불이 이 자리를 지나갔는지 또한 함께 살펴보아야 한다.

이 부분을 간과하지 못해 계속 틀린 답을 제출했는데 나와 같은 실수를 하는 사람이 없길 바란다.

 

가령, 

4 5
#####
#...#
#.J.#
#...#

와 같이 , 불이 주어지지 않는 케이스에서 이 부분을 고려하지 않는다면, 충분히 탈출 할 수 있음에도 IMPOSSIBLE을 출력한다.

 

이 모든 과정을 지나면서 시간을 출력하지 않은 경우, 즉 이 과정들 속에서 프로그램이 종료하지 않았다면

지훈이는 탈출할 수 없다는 의미이므로 IMPOSSIBLE 을 출력한다.

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int cx[4] = {0,1,0,-1}; //좌표의 상하좌우를 살펴볼 X 좌표
int cy[4] = {1,0,-1,0};//좌표의 상하좌우를 살펴볼 y 좌표
char board[1002][1002]; //미로
int fvisit[1002][1002]; //불이 지나간 시간
int jvisit[1002][1002]; //지훈이가 지나간 시간
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int r, c;
	cin >> r >> c;

	memset(fvisit, -1, sizeof(fvisit)); //-1로 초기화해야 탐색했는지 여부와 시간을 용이하게 저장할 수 있음
 	memset(jvisit, -1, sizeof(jvisit)); 

	queue<pair<int, int>>ji; //지훈이 좌표 저장 큐
	queue<pair<int, int>>f; //불 좌표 저장 큐
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'J') {
				ji.push({ i,j });
				jvisit[i][j] = 0;
			}
			else if (board[i][j] == 'F') {
				f.push({ i,j });
				fvisit[i][j] = 0;
			}
		}
	}
	while (!f.empty()) { //불 bfs
		pair<int, int>cur = f.front();
		f.pop();
		for (int k = 0; k < 4; k++) {
			int dx = cur.first + cx[k];
			int dy = cur.second + cy[k];
			if (dx < 0 || dx >= r || dy < 0 || dy >= c) continue;
			if (board[dx][dy] == '#' || fvisit[dx][dy] >= 0) continue;

			f.push({ dx,dy });
			fvisit[dx][dy] = fvisit[cur.first][cur.second] + 1;
		}
	}
	while (!ji.empty()) {//지훈이 bfs
		pair<int, int>cur = ji.front();
		ji.pop();
		for (int k = 0; k < 4; k++) {
			int dx = cur.first + cx[k];
			int dy = cur.second + cy[k];
			if (dx < 0 || dx >= r || dy < 0 || dy >= c) {
				cout << jvisit[cur.first][cur.second] + 1;
				return 0;
			}
			if (board[dx][dy] == '#' || jvisit[dx][dy] >= 0) continue;
			if (fvisit[dx][dy]!=-1&&jvisit[cur.first][cur.second] + 1 >= fvisit[dx][dy]) continue;
			ji.push({ dx,dy });
			jvisit[dx][dy] = jvisit[cur.first][cur.second] + 1;
		}
	}

	cout << "IMPOSSIBLE"; //탈출 불가능
}

3) 참고자료