[ 백준 3197 ] 백조의 호수 (C++)

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

3197번: 백조의 호수

 

효율성을 고려해야 하는 문제다. 푸는데 꽤 오래 걸렸다... 문제를 읽어보면 알겠지만 얼핏 보면 어려운 문제로 보이지 않는다. 그냥 bfs 또는 dfs를 계속 사용하면 테스트 케이스는 통과한다. 그런데 그렇게 풀면 무조건 시간초과에 걸릴 것이다. 이 문제는 단 한번의 bfs로 해결해야 하는 문제다.

 

전체적인 알고리즘은 '경로탐색 -> 얼음 녹이기'를 반복하면 된다. 그런데 이를 한 번의 bfs로 해결해야 한다. 따라서 엄밀히 말하면 '초기 입력값에서 경로탐색 -> 1일차 얼음 녹이기 -> 새로 생긴 길로 재탐색 -> 2일차 얼음 녹이기 -> ...' 과정을 반복해야 한다. 백조는 이미 방문한 위치를 재방문해서는 안되고, 얼음을 녹일 때도 map 전체를 검사해서는 안 된다. 이를 어떻게 구현할 수 있을까? 

 

나는 네 개의 큐를 사용했다. 각각 설명은 아래와 같다. 

 

queue<pair<int, int>> swan // 백조의 이동 위치
queue<pair<int, int>> next_swan // 백조의 다음 이동 위치 
queue<pair<int, int>> water // 물의 위치
queue<pair<int, int>> next_water // 녹은 물의 위치

 

next_swan 에는 어떤 위치가 들어가야 할까? 다음 턴에서 백조가 시작해야 하는 위치는? 잘 생각해보자. 백조는 경로 탐색을 하다가 얼음을 만나면 멈춘다. 얼음은 녹으면 새로운 길이 된다. 따라서 백조가 만나는 얼음의 위치들을 next_swan에 저장하면 된다. 

 

next_water에는 어떤 위치가 들어가야 할까? 다음 턴에 녹는 얼음들은 모두 물과 맞닿아있는 점들이다. 따라서 물과 맞닿아아 있는 얼음의 위치들을 next_water에 저장하면 된다. 

 

bfs는 swan, water 모두 각각 함수를 정의해줘야 한다. 위에서 설명한 것들이 bfs 함수에서 구현된다. 각 bfs 함수에서 next_swan과 next_water에 어떤 값들이 들어가는지 주목해서 보자.

 

먼저 swan_bfs() 는 아래와 같다. 설명은 주석을 참고하자.

 

// 경로탐색 하다가 얼음 만나면 얼음 위치를 next에 push
void swan_bfs() {
	while (!swan.empty() && !Find) {
		int x = swan.front().first;
		int y = swan.front().second;
		swan.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
				if (!visit[xx][yy]) {
					if (map[xx][yy] == 'X') {
						// 1. 얼음인 경우
						visit[xx][yy] = 1;
						next_swan.push({ xx, yy });
					}
					else if (map[xx][yy] == '.') {
						// 2. 물인 경우
						visit[xx][yy] = 1;
						swan.push({ xx, yy });
					}
					else if (map[xx][yy] == 'L') {
						// 3. 백조인 경우
						visit[xx][yy] = 1;
						Find = 1;
						swan.push({ xx, yy });
					}
				}
			}
		}
	}
}

 

다음 위치가 얼음인 경우, 물인 경우, 백조인 경우로 나뉘는 것을 볼 수 있다. 얼음인 경우 방문 처리를 하고 그 위치를 next_swan에 push해준다. 방문처리를 하는 이유는 원래 bfs에서 초기에 들어가는 값들은 방문처리를 해주기 때문이다. 다음 위치가 물인 경우 방문 처리를 하고 그 위치를 swan에 push 해준다. 이는 추가적인 경로탐색을 해주기 위함이다. 마지막으로 다음 위치가 백조인 경우 목적지에 도달한 것이므로 추가로 볼 필요가 없다. while 문에서 Find를 조건으로 넣어줌으로써 Find가 참이 되면 while 문이 멈추게 된다.

 

 

이제 water_bfs() 함수를 살펴보자.

// 얼음과 닿아 있으면 next에 push 하고 물로 바꿔준다
void water_bfs() {
	while (!water.empty()) {
		int x = water.front().first;
		int y = water.front().second;
		water.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
				if (map[xx][yy] == 'X') {
					map[xx][yy] = '.';
					next_water.push({ xx, yy });
				}
			}
		}
	}
}

 

water_bfs() 함수는 크게 어려운게 없다. 위 주석대로 그냥 다음 위치가 얼음이면 물로 바꿔주고 그 위치를 next_water에 push 해주면 된다. 왜냐? 다음 터에 물로 변하는 대상은 물과 맞닿아있는 얼음의 위치이기 때문이다. 

 

 

필요한 함수는 모두 설명했다. 이제 메인 함수를 살펴보자. 아주 간단하다. 백조끼리 만날때까지 경로 탐색을 해주고, 얼음을 녹이고를 반복하면 된다. 

while (!Find) {
    swan_bfs(); // 경로 탐색 먼저 한다.
    water_bfs(); // 얼음 녹인다

    // 다음 위치를 현재로
    swan = next_swan;
    water = next_water;
	
    // 큐 비워주기
    while (!next_swan.empty()) next_swan.pop();
    while (!next_water.empty()) next_water.pop();

    day++;
}

 

 

정답 코드는 아래와 같다. 

 

#include <iostream>
#include <queue>
#define endl '\n';
using namespace std;

queue<pair<int, int>> water;
queue<pair<int, int>> next_water;
queue<pair<int, int>> swan;
queue<pair<int, int>> next_swan;
char map[1501][1501];
int visit[1501][1501];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int R, C, swan_x, swan_y;
int Find = 0;

// 경로탐색 하다가 얼음 만나면 얼음 위치를 next에 push
void swan_bfs() {
	while (!swan.empty() && !Find) {
		int x = swan.front().first;
		int y = swan.front().second;
		swan.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
				if (!visit[xx][yy]) {
					if (map[xx][yy] == 'X') {
						// 1. 얼음인 경우
						visit[xx][yy] = 1;
						next_swan.push({ xx, yy });
					}
					else if (map[xx][yy] == '.') {
						// 2. 물인 경우
						visit[xx][yy] = 1;
						swan.push({ xx, yy });
					}
					else if (map[xx][yy] == 'L') {
						// 3. 백조인 경우
						visit[xx][yy] = 1;
						Find = 1;
						swan.push({ xx, yy });
					}
				}
			}
		}
	}
}


// 얼음과 닿아 있으면 next에 push 하고 물로 바꿔준다
void water_bfs() {
	while (!water.empty()) {
		int x = water.front().first;
		int y = water.front().second;
		water.pop();

		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
				if (map[xx][yy] == 'X') {
					map[xx][yy] = '.';
					next_water.push({ xx, yy });
				}
			}
		}
	}
}

int main() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'L') {
				swan_x = i;
				swan_y = j;
			}
			if (map[i][j] != 'X') {
				water.push({ i, j });
			}
		}
	}

	int day = 0;

	swan.push({ swan_x, swan_y });
	visit[swan_x][swan_y] = 1;

	while (!Find) {
		swan_bfs(); // 경로 탐색 먼저 한다.
		water_bfs(); // 얼음 녹인다
		
		swan = next_swan;
		water = next_water;
		
		while (!next_swan.empty()) next_swan.pop();
		while (!next_water.empty()) next_water.pop();

		day++;
	}

	cout << day - 1 << endl;

	return 0;
}