BOJ - 백조의 호수(3197)

BFS를 응용해서 풀 수 있는 문제입니다. 빙판을 녹일 때는 Queue에 들어 있는 물을 하나씩 빼면서 근처에 있는 빙하를 녹입니다. 녹아서 새로 생긴 물은 다시 Queue에 넣어주는데 보관하고 있다가 다음 날 빙판을 녹이는 데 사용합니다.

빙판을 녹인 후 백조가 만날 수 있는지 확인해야 합니다. 그런데 매일매일 백조가 다른 백조를 만날 수 있는지 처음부터 확인하면 Timeout이 발생합니다. 이 문제를 해결하기 위해서는 백조가 갈 수 있는 마지막 위치를 보관하고 있다가 다음 날 그 부분부터 시작해야 합니다.

Queue 두 개를 사용해서 해결할 수 있습니다. 백조가 물을 따라서 BFS를 수행하다가 빙판을 만나면 다음 날에 사용할 다른 Queue에 넣어줍니다. 백조가 다른 백조를 만나지 못하고 하루가 끝나면, 다음 날 다른 Queue를 이용해서 백조가 다른 백조를 만날 수 있는지를 확인합니다.

풀이 코드

// 얼음을 녹이는 것은 순차적으로 진행
// 백조를 이동시킬 때 Queue를 두 개 사용해서,
// 다음 순서 때 백조 위치를 이전 턴 마지막부터 시작한다.

#include <iostream>
#include <stdio.h>

using namespace std;

#define MAX_MAP 1500
#define MAX_QUEUE 2250000

int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

int R, C;

int swan[2][2];
int swan_idx;

char lake[MAX_MAP][MAX_MAP];
int lake_queue[MAX_QUEUE][2];

int lake_head;
int lake_tail;

int** swan_queue;
int swan_queue_1[MAX_QUEUE][2];
int swan_queue_2[MAX_QUEUE][2];

int swan1_head;
int swan1_tail;

int swan2_head;
int swan2_tail;

bool swan_visited[MAX_MAP][MAX_MAP];

// 얼음 녹이기
void bfs_lake() {
	int count = lake_tail - lake_head;

	// 현재 queue에 등록된 물 주위만 빙하를 녹이고 종료
	while (count--) {

		// dequeue
		int y = lake_queue[lake_head][0];
		int x = lake_queue[lake_head][1];
		lake_head++;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (lake[ny][nx] == 'X') {
				lake[ny][nx] = '.';

				// enqueue, 다음 물 주위 빙하를 녹이기 위해 등록
				lake_queue[lake_tail][0] = ny;
				lake_queue[lake_tail][1] = nx;
				lake_tail++;
			}
		}
	}
}

// 백조 움직이기
bool bfs_swan() {

	while (swan1_tail != swan1_head) {

		// dequeue
		int y = swan_queue_1[swan1_head][0];
		int x = swan_queue_1[swan1_head][1];
		swan1_head++;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (swan_visited[ny][nx] == true) continue;
			else {
				
				// 만난 경우
				if (ny == swan[1][0] && nx == swan[1][1]) {
					return true;
				}

				if (lake[ny][nx] == '.') {
					// enqueue
					swan_queue_1[swan1_tail][0] = ny;
					swan_queue_1[swan1_tail][1] = nx;
					swan1_tail++;
				} else {
					// 다음에 이어서 탐색하기 위해 
					swan_queue_2[swan2_tail][0] = ny;
					swan_queue_2[swan2_tail][1] = nx;
					swan2_tail++;
				}

				// visited, 다음에 이어서 탐색할 것도 queue에 들어갔기 때문에 visited 시킨다.
				swan_visited[ny][nx] = true;
			}

		}
	}
	return false;
}

int main() {
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		cin >> lake[i];
		for (int j = 0; j < C; j++) {
			if (lake[i][j] == 'L') {
				lake[i][j] = '.';
				swan[swan_idx][0] = i;
				swan[swan_idx][1] = j;
				swan_idx++;
			}
			if (lake[i][j] == '.') {
				lake_queue[lake_tail][0] = i;
				lake_queue[lake_tail][1] = j;
				lake_tail++;
			}
		}
	}

	// init queue
	swan1_head = 0;
	swan1_tail = 0;

	// enqueue
	swan_queue_1[swan1_tail][0] = swan[0][0];
	swan_queue_1[swan1_tail][1] = swan[0][1];
	swan1_tail++;

	swan_visited[swan[0][0]][swan[0][1]] = true;

	int ans = 0;
	while (bfs_swan() == false) {

		// 저장해둔 백조 마지막 경로들 옮기기
		swan1_head = 0;
		swan1_tail = 0;
		while (swan2_head != swan2_tail) {
			swan_queue_1[swan1_tail][0] = swan_queue_2[swan2_head][0];
			swan_queue_1[swan1_tail][1] = swan_queue_2[swan2_head][1];
			swan1_tail++;
			swan2_head++;
		}

		// 빙하 녹이기
		bfs_lake();

		ans++;
	}

	printf("%d", ans);
}