이번에는 백준 3197번 백조의 호수 문제를 풀어보았습니다.
문제를 처음 봤을 때 단순히 백조만 이동시키는 BFS로는 해결할 수 없다고 생각했습니다.
시간이 지남에 따라 얼음이 계속 녹고, 백조도 녹은 물을 따라 계속 이동해야 하기 때문입니다.
그래서 얼음을 녹이는 BFS와 백조를 이동시키는 BFS를 각각 수행하도록 구현하였습니다.
또한 하루가 지날 때마다 새롭게 탐색해야 하는 영역만 관리하기 위해 Flood Fill 방식으로 구현하였습니다.
문제 설명
호수에는 물(.), 얼음(X), 백조(L)가 존재합니다.
매일 물과 접촉한 모든 얼음은 녹게 됩니다.
백조는 물 위에서만 이동할 수 있으며, 얼음이 녹으면 그 위치로 이동할 수 있습니다.
두 백조가 만날 수 있는 최소 날짜를 구하는 문제입니다.
풀이 아이디어
이 문제는 크게 두 가지 BFS가 필요하다고 생각했습니다.
첫 번째는 얼음을 녹이는 BFS입니다.
현재 물과 접촉한 얼음만 다음 날 녹기 때문에 현재 물 영역을 계속 확장하면서 다음 날 녹을 얼음을 따로 저장하였습니다.
두 번째는 백조를 이동시키는 BFS입니다.
현재 이동 가능한 물은 바로 탐색하고, 얼음을 만나면 그 위치를 다음 날 다시 탐색하도록 따로 저장하였습니다.
따라서 백조 BFS와 얼음 BFS를 각각 수행하면서 하루가 끝날 때마다 다음에 탐색할 큐로 교체하는 방식으로 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
queue<pair<int, int>> swan;
queue<pair<int, int>> water;
int day;
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
int water_visited[1501][1501];
int swan_visited[1501][1501];
char lake_map[1501][1501];
int main() {
int N,M;
cin >> M >> N;
bool swan_once = false;
for (int i=1; i<=M; i++) {
string s;
cin >> s;
for (int j=1; j<=N; j++) {
lake_map[i][j] = s[j-1];
if (lake_map[i][j] == 'L' && !swan_once) {
swan_once = true;
swan_visited[i][j] = 1;
swan.push({i, j});
lake_map[i][j] = '.';
}
else if (lake_map[i][j] != 'X')
{
water.push({i,j});
water_visited[i][j] = 1;
}
}
}
while(true) {
queue<pair<int, int>> next_swan;
queue<pair<int, int>> next_water;
while(!swan.empty()) {
pair<int,int> curr_swan = swan.front();
swan.pop();
if (lake_map[curr_swan.first][curr_swan.second] == 'L') {
cout << day << '\n';
return 0;
}
for (int i=0; i<4; i++) {
int ny = curr_swan.first + dy[i];
int nx = curr_swan.second + dx[i];
if (ny < 1 || ny > M || nx < 1 || nx > N) continue;
if (swan_visited[ny][nx]) continue;
if (lake_map[ny][nx] == 'X') {
next_swan.push(make_pair(ny, nx));
} else {
swan.push(make_pair(ny, nx));
}
swan_visited[ny][nx] = 1;
}
}
while(!water.empty()) {
pair<int, int> curr_water = water.front();
water.pop();
for (int i=0; i<4; i++) {
int ny = curr_water.first + dy[i];
int nx = curr_water.second + dx[i];
if (ny < 1 || ny > M || nx < 1 || nx > N) continue;
if (water_visited[ny][nx]) continue;
if (lake_map[ny][nx] == 'X') {
next_water.push(make_pair(ny, nx));
lake_map[ny][nx] = '.';
}
water_visited[ny][nx] = 1;
}
}
swan = next_swan;
water = next_water;
day++;
}
return 0;
}풀이 흐름
- 첫 번째 백조를 시작점으로 저장합니다.
- 현재 물인 모든 위치를 water 큐에 저장합니다.
- 백조 BFS를 수행하여 현재 이동 가능한 물 영역을 모두 탐색합니다.
- 얼음을 만나면 다음 날 이동하기 위해 next_swan 큐에 저장합니다.
- 물 BFS를 수행하여 현재 물과 맞닿아 있는 얼음을 녹입니다.
- 새롭게 녹은 얼음은 next_water 큐에 저장합니다.
- 하루가 끝나면 next 큐들을 현재 큐로 교체하고 날짜를 증가시킵니다.
- 다른 백조를 만나면 현재 날짜를 출력합니다.
구현 포인트
1. 첫 번째 백조를 시작점으로 설정
입력을 받으면서 첫 번째 백조를 BFS의 시작점으로 사용하였습니다.
if (lake_map[i][j] == 'L' && !swan_once) {
swan_once = true;
swan_visited[i][j] = 1;
swan.push({i, j});
lake_map[i][j] = '.';
}첫 번째 백조는 물처럼 취급하기 위해 '.'으로 변경하였습니다.
2. 백조 BFS
현재 이동 가능한 물은 바로 탐색하고, 얼음은 다음 날 탐색하도록 분리하였습니다.
if (lake_map[ny][nx] == 'X') {
next_swan.push(make_pair(ny, nx));
} else {
swan.push(make_pair(ny, nx));
}현재 날짜에 갈 수 있는 영역은 모두 Flood Fill 방식으로 탐색하였습니다.
3. 얼음 녹이기 BFS
현재 물과 맞닿아 있는 얼음을 녹였습니다.
if (lake_map[ny][nx] == 'X') {
next_water.push(make_pair(ny, nx));
lake_map[ny][nx] = '.';
}오늘 녹은 얼음은 다음 날부터 물이 되므로 next_water에 저장하였습니다.
4. 다음 날짜에 탐색할 영역 관리
이 문제의 핵심이었던 부분입니다.
백조와 물 모두 현재 탐색이 끝난 뒤 다음 날짜에 다시 탐색해야 했기 때문에 각각 next 큐를 사용하였습니다.
queue<pair<int, int>> next_swan;
queue<pair<int, int>> next_water;현재 날짜에 확장 가능한 영역은 모두 탐색하고, 경계에 있는 영역만 다음 날짜로 넘기는 Flood Fill 방식으로 구현하였습니다.
5. 날짜 증가
현재 날짜의 탐색이 모두 끝나면 다음 날짜의 큐로 교체하였습니다.
swan = next_swan;
water = next_water;
day++;이 과정을 반복하면서 백조가 만나는 날짜를 구하였습니다.
6. 다른 백조를 만나면 종료
탐색 중 다른 백조 위치에 도달하면 현재 날짜를 출력하였습니다.
if (lake_map[curr_swan.first][curr_swan.second] == 'L') {
cout << day << '\n';
return 0;
}현재 day가 두 백조가 만날 수 있는 최소 날짜가 됩니다.
