[C++] BOJ(백준) 4179 불!

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

4179번: 불!

 

BFS 문제다.

 

문제 이해에 이틀을 쓴 것 같다...ㅋ

불도 사람처럼 1분에 한 칸만 움직이는 줄 알았는데 불은 1분에 4방향으로 다 퍼지는 것이었다.

이 부분을 해결하고 나니 첫 번째 의문은 해결됐고 다른 의문이 생겼다.

 

몇 분이 걸리는지가 중요한 문제이기 때문에 한 타임에 딱 한 번만 움직여야 하는데 그 부분 구현이 의문이었다.

나는 큐의 사이즈를 구한 후 그만큼만 돌리면 된다고 생각했는데

뭔가 비효율적인 느낌이 들어서 한참을 고민하다가 결국은 이 방법을 선택했다.

 

BFS의 while문 조건은 사람 큐의 비었는지 여부로 확인했다.

사람 탈출의 여부가 문제 이기 때문에 불 큐의 비었는지 여부로는 종료 조건이 될 수 없다고 생각했다.

BFS 내부에서는 불에 대한 반복문, 사람에 대한 반복문을 진행했다.

불은 사람보다 먼저 퍼져야 하고, 불이 퍼진 자리는 사람이 갈 수 없다.

불과 사람이 갈 수 있는 칸이 동일하다면 사람은 갈 수 없기 때문이다.

불이 지나간 자리도 #으로 바꿔 벽처럼 취급했다.

 

추가로 입력받을 때 탈출구를 표시해 뒀다.

#include <iostream>
#include <queue>
using namespace std;

int n, m;
char board[1000][1000];
bool pisit[1000][1000];	// 사람의 방문 체크
bool fisit[1000][1000];	// 불의 방문 체크
// 상하좌우 탐색을 위함
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

queue<pair<int, int>> pq;	// 사람 큐
queue<pair<int, int>> fq;	// 불 큐

void BFS() {
	int cnt = 0;

	// 큐가 빌 때까지 반복
	while (!pq.empty()) {
		cnt++;

		int fize = fq.size();
		int pize = pq.size();

		for (int i = 0; i < fize; i++) {
			int fr = fq.front().first;
			int fc = fq.front().second;

			fq.pop();

			for (int j = 0; j < 4; j++) {
				int r = fr + dr[j];
				int c = fc + dc[j];

				// 범위를 벗어나면 continue
				if (r < 0 || c < 0 || r >= n || c >= m) continue;
				// 방문한 적이 있으면 continue
				if (fisit[r][c]) continue;
				// 벽이면 continue
				if (board[r][c] == '#') continue;

				fq.push({ r,c });
				fisit[r][c] = 1;
				board[r][c] = '#';
			}
		}

		for (int i = 0; i < pize; i++) {
			int pr = pq.front().first;
			int pc = pq.front().second;

			pq.pop();

			for (int j = 0; j < 4; j++) {
				int r = pr + dr[j];
				int c = pc + dc[j];

				// 범위를 벗어나면 continue
				if (r < 0 || c < 0 || r >= n || c >= m) continue;
				// 방문한 적이 있으면 continue
				if (pisit[r][c]) continue;
				// 벽이면 continue
				if (board[r][c] == '#') continue;

				// 탈출 가능하면 출력 후 종료
				if (board[r][c] == 'o') {
					cout << cnt + 1;
					return;
				}
				pq.push({ r,c });
				pisit[r][c] = 1;
			}
		}
	}
	cout << "IMPOSSIBLE";
	return;
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];

			// 불 입력 시 불 큐에 추가, 벽과 같이 갈 수 없는 공간으로 취급
			if (board[i][j] == 'F') {
				fq.push({ i, j });
				fisit[i][j] = 1;
				board[i][j] = '#';
			}

			// 사람 입력 시 사람 큐에 추가
			else if (board[i][j] == 'J') {
				pq.push({ i, j });
				pisit[i][j] = 1;
			}

			// 테두리 중 벽이 아니라면 별도 표기로 출구임을 나타냄
			if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
				if (board[i][j] == '.') board[i][j] = 'o';
				else if (board[i][j] == 'J') {
					cout << 1;
					return 0;
				}
			}
		}

	BFS();
}

고민한 거에 비해 너무 쉽게 풀렸다.