[백준] 4179번 불!

www.acmicpc.net/problem/4179

4179번: 불!

생각해낸 방식이 마음에 들어서 포스팅해놓으려한다.

방식은 조금 복잡한데 옛날에 풀었던 것보다 시간이 1/4정도 줄었다.

 

큐를 하나만 이용해서 풀었다.

말로 어떻게 풀어야될지 잘 모르겠는데 시간에 따른 J와 F를 J1,J2,J3... 과 F1,F2,F3...로 표현하겠다.

1. 처음 큐에 F1F1J1과 같이 F를 앞에 J를 제일 뒤에 넣어준다. (불을 먼저 번지게 하고 사람이 움직이는게 더 간단하다.)

2. BFS과정을 통해 시간이 지남에 따라 큐에는 F1J1 F2J2 F3J3 F4J4와 같이 시간 순서대로 들어있게 된다.

(물론 앞에 순서는 POP되지만 가독성을 위해 같이 써놨다.)

3. 큐에는 pair<pair<int, int>>의 형태로 제일 앞에는 불이면 0을 사람이면 1이상의 숫자와 좌표로 구성된 데이터가 들어간다. (사람일 경우 앞의 숫자는 탈출 시간을 의미한여 BFS과정에서 기준점 숫자 + 1로 큐에 넣는다.)

4. 위 과정을 수행하는 중에 사람이 테두리에 도착하면 그 때 큐에 저장되어 있던 숫자 + 1이 걸린 시간이 된다.

 

옛날에 풀었을 때 장애물 없이

1 2

J K

와 같은 경우들이 반례로 있었던 것 같아서 위와 같은 경우들을 반례로 처리했다.

#include <iostream>
#include <queue>

using namespace std;

char board[1000][1000];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int N, M;
pair<int, int> cur_F;
pair<int, int> cur_J;
queue<pair<int, pair<int, int>>> q;

int BFS() {
	while (!q.empty()) {
		pair<int, pair<int, int>> cur;
		cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.second.first + dx[dir];
			int ny = cur.second.second + dy[dir];

			if (nx < 0 || ny < 0 || nx >= N || ny >= M)
				continue;

			if (board[nx][ny] != '#' && board[nx][ny] != 'F') {
				if (cur.first == 0) {
					board[nx][ny] = 'F';
					q.push({ 0, { nx, ny } });
				}
				else if (cur.first != 0) {
					if (board[nx][ny] == '.') {

						if (nx == 0 || ny == 0 || nx == N - 1 || ny == M - 1) {
							return cur.first + 1;
						}

						board[nx][ny] = 'J';
						q.push({ cur.first + 1, {nx, ny} });
					}
				}
			}
		}
	}
	return 0;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> board[i];
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'J')
				cur_J = { i, j };
			if (board[i][j] == 'F')
				q.push({ 0, {i, j} });
		}
	}
	q.push({ 1, cur_J });

	if (cur_J.first == 0 || cur_J.second == 0 || cur_J.first == N - 1 || cur_J.second == M - 1) {
		cout << 1;
		return 0;
	}

	int result = BFS();
	if (result == 0)
		cout << "IMPOSSIBLE";
	else
		cout << result;
}