알고리즘 :: 백준 :: 4179 - 불!

 

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 행 R, 열 C (1 ≤ R, C ≤ 1000)
• 지훈이 위치는 오직 1개
• 탈출할 수
  • 있다면 탈출까지 걸린 최소시간
  • 없다면 "IMPOSSIBLE" 출력

✏️ 문제풀이

동시성 구현

이 문제에서 가장 까다로운건 '동시성'을 어떻게 해결할지에 대한 고민입니다. 불과 지훈이는 동시에 이동하기 때문입니다.

• 기존 BFS를 돌릴 때, 우리는 큐가 빌 때까지 돌리기 위해 `while(!q.empty())`를 관용구 처럼 사용했습니다.
• 하지만, 이번에는 다릅니다. 현재 시간에 큐에 들어있는 요소들을 처리하는 동안 다음 시간에 이동할 예정인 칸들이 큐에 들어오기 때문입니다. 이것들은 '지금' 처리하면 안 되겠지요.
• 이러한 문제에서 '지금', '현재' 큐에 들어있는 요소만 처리하기 위해서 for문을 사용합니다.

int size = q.size();	// '현재' 큐에 들어있는 요소 개수
// '현재' 요소 개수만큼만 계산합니다.
for (int i = 0; i < size; ++i) {
	...
}
// for문이 끝났을 때 큐에는 '다음 시간'에 계산할 요소들만 들어 있습니다.

이동은 누가 먼저

다음 고민은 불과 지훈이의 이동을 어떻게 처리할지에 대해서 입니다.

• 불이 먼저 이동합니다. 직후에 불이 확산되는 곳을 표시합니다.
• 표시는 'F'로 그냥 불이 번진것과 똑같지만, 우리 마음속에는 '불이 번질 예정인 곳, 지훈이가 가면 죽는 곳' 이라고 생각하면 됩니다.
• 지훈이는 벽, 불 (그리고 불이 번질 예정인 곳) 이외의 빈칸으로 이동하면 됩니다.
• 그리고 문제에는 불이 지훈이가 있는 곳에 가면 안 된다는 법이 없습니다. 불은 지훈이가 있는 칸을 빈칸이라고 봅니다.

요약하면 로직은 다음과 같습니다.

while (!지훈이_위치_큐.empty()) {
	불_이동();
    지훈_이동();
    if (지훈_탈출) { 정답출력; 프로그램 종료; }
    시간++;
}

 

범위 조심하기

이제 남은건 범위만 조심해주면 됩니다. 예제 입출력이 도움이 됩니다.

이 문제에서 지훈이의 탈출조건은 미로의 가장자리로 벗어났을 때 입니다.

따라서 양쪽 가장자리에 여유를, 즉 행과 열에 두 칸씩 여유를 주셔야 합니다.

• 저는 미로를 1번~R번행 / 1번~C번행에 저장했습니다.
• 지훈이가 0번행 또는 0번열 또는 R + 1번 행 또는 C + 1번 행에 도착했을 때 '탈출' 했다고 인정합니다.

그러므로, 불과 지훈이에 대해서 BFS를 돌릴 때, 다음 칸을 큐에 저장하는 조건을 신경써야 합니다.

• 불: `arr[1~R][1~C]` 내에서 움직입니다.
• 지훈: `arr[0~R+1][0~C+1]` 내에서 움직입니다.
• 지훈이 범위 햇갈리면 가장자리를 큐에 못 넣어서 탈출 못 합니다. 조심하세요. 

📝 코드

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

constexpr int N = 1002;
constexpr int dy[] = {1, 0, -1, 0};
constexpr int dx[] = {0, 1, 0, -1};

int R, C, ans;
bool visitedMan[N][N];
bool visitedFire[N][N];
array<array<char, N>, N> arr;
queue<pair<int, int>> man, fire;

void goFire() {
	int sz = fire.size();
	for (int i = 0; i < sz; ++i) {
		int y, x; tie(y, x) = fire.front();
		fire.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 1 || ny > R || nx < 1 || nx > C) continue;
			if (arr[ny][nx] == '#' || visitedFire[ny][nx]) continue;
			
			arr[ny][nx] = 'F';
			visitedFire[ny][nx] = true;
			fire.push({ny, nx});
		}
	}
}

bool goJihoon() {
	int sz = man.size();
	for (int i = 0; i < sz; ++i) {
		int y, x; tie(y, x) = man.front();
		man.pop();
		
		if (y == 0 || y == R + 1 || x == 0 || x == C + 1) return true;
		
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny > R + 1 || nx > C + 1) continue;
			if (visitedMan[ny][nx] || arr[ny][nx] == '#' || arr[ny][nx] == 'F') continue;
			visitedMan[ny][nx] = true;
			man.push({ny, nx});
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> R >> C;
	
	for (int y = 1; y <= R; ++y) {
		string line;
		cin >> line;
		for (int x = 1, xx = 0; x <= C; ++x, ++xx) {
			arr[y][x] = line[xx];
			if (line[xx] == 'F') {
				fire.push({y, x});
				visitedFire[y][x] = true;
			} else if (line[xx] == 'J') {
				man.push({y, x});
				visitedMan[y][x] = true;
			}
		}
	}
	while (!man.empty()) {
		goFire();
		if (goJihoon()) { cout << ans; return 0; }
		ans++;
	}
	cout << "IMPOSSIBLE";
}

 

🔗 코드 링크

🕧 결과