[백준 / C++] 4179번: 불!

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

4179번: 불!

난이도: solved.ac 골드 4

 

알고리즘 분류

그래프 탐색 (BFS)

 

접근 방법

J가 F와 동시에 같은 지점으로 이동하면 불에 타 죽는다. 따라서 먼저 F를 이동시킨 후 J를 이동시키는 방법으로 진행했다.

 

다른 분들은 BFS를 두 번 돌리던데, 하나의 BFS 큐에 J와 F를 넣어서 BFS를 한 번만 돌려도 이 문제를 풀 수 있다. (이렇게 하면 메모리나 시간을 훨씬 단축시킬 수 있다.)

먼저 F를 큐에 넣고 J를 큐에 넣어 BFS를 진행하면 매 분마다 F와 J가 이동하는 걸 각각 구현할 수 있다.

 

input에서 J는 딱 하나 주어지므로 J의 좌표를 따로 저장하고 F는 곧바로 queue에 넣어준다. 그리고 모든 input을 받으면 저장해 둔 J의 좌표를 queue에 넣어준다.

 

그럼 queue의 top에는 F가 있는데, 이를 pop해서 인접한 상하좌우에 #(벽)이 없으면 해당 좌표를 queue에 넣는다. 이는 1분이 지났을 때의 F의 위치가 된다.

queue에서 J가 나오기 전까지 F를 pop하고 #이 아닌 곳의 좌표를 push 하는 과정을 진행하면, 새로 queue에 들어온 F들은 모두 1분이 지날 때의 F의 위치가 된다.

그리고 top에 있는 J를 pop 해서 인접한 상하좌우에 #이나 F가 아닌 .가 있으면 그 위치를 queue에 push 해준다.

이는 1분이 지날 때의 J의 가능한 위치가 된다.

 

그다음 J가 나오기 전까지 모든 F를 pop 해서 또 인접한 상하좌우의 #가 아닌 곳의 좌표를 push해주면 이는 2분이 지날 때의 F의 위치이고, 그 다음 J를 pop해서 인접한 상하좌우의 .인 지점의 좌표를 push 해주면 이는 2분이 지날 때의 J의 위치가 된다.

 

이 과정을 queue가 비거나 J의 좌표가 미로의 테두리에 위치할 때까지 해준다.

 

그리고 구해야하는 것은 J가 탈출하는 시간이므로 시간도 좌표와 함께 pair로 묶어 저장하는데, J에만 시간을 주어 F와 구별되게 하였다. (F는 시간 값을 0으로 주었다.)

 

코드

#include <bits/stdc++.h>
using namespace std;

int R, C, ans;
char arr[1000][1000];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
queue<pair<pair<int, int>, int>> q;
// q에서 first는 F또는 J의 좌표, second는 J의 시간 (시간은 1부터 시작)
// 따라서 second가 0이면 F, 1 이상이면 J 
// J가 테두리에 다다르면 BFS를 종료함
void BFS();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> R >> C;
	int i, j, jy, jx;
	// 매 시간마다 불이 먼저 퍼진 후 지훈이가 움직여야 하므로
	// 입력을 받으며 F를 먼저 queue에 넣어줌
	for (i = 0; i < R; i++)
		for (j = 0; j < C; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'J') {
				jy = i;
				jx = j;
			}
			else if (arr[i][j] == 'F')
				q.push(make_pair(make_pair(i, j), 0));
		}
	// J를 queue에 넣어주고, 시간은 1부터 시작
	q.push(make_pair(make_pair(jy, jx), 1));
	BFS();
	if (ans)
		cout << ans;
	else
		cout << "IMPOSSIBLE";
}

void BFS() {
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int t = q.front().second;
		q.pop();
		if ((y == 0 || y == R - 1 || x == 0 || x == C - 1) && t) {
			ans = t;
			return;
		}
		for (int dir = 0; dir < 4; dir++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny >= 0 && ny < R && nx >= 0 && nx < C) {
				// t가 1이상이면 J, 0이면 F
				if (t) {
					if (arr[ny][nx] == '.') {
						// J의 이동경로를 저장하기 위해 J로 바꿔줌
						arr[ny][nx] = 'J';
						// 시간 1 증가해서 queue에 넣음
						q.push(make_pair(make_pair(ny, nx), t + 1));
					}
				}
				else {
					if (arr[ny][nx] == '.' || arr[ny][nx] == 'J') {
						// F가 이동할 위치를 F로 바꿔줌
						arr[ny][nx] = 'F';
						q.push(make_pair(make_pair(ny, nx), 0));
					}
				}
			}
		}
	}
}

 

성능

코드 제출 결과