이번에는 백준 3197번 백조의 호수 문제를 풀어보았습니다.
처음에는 얼음을 녹이는 과정과 백조를 이동시키는 과정을 따로 생각해야 한다고 생각했습니다.
백조는 물 위에서만 이동할 수 있고, 얼음은 하루가 지날 때마다 물과 접촉한 부분이 녹게 됩니다.
따라서 얼음을 녹이는 BFS와 백조를 이동시키는 BFS를 각각 수행하면서 두 백조가 만나는 날짜를 찾도록 구현하였습니다.
문제 설명
호수에는 물과 얼음이 존재합니다.
얼음은 매일 물과 접촉한 부분이 녹게 됩니다.
백조는 물 위에서만 이동할 수 있으며 상하좌우로 이동할 수 있습니다.
두 백조가 만날 수 있게 되는 최소 날짜를 구하는 문제입니다.
풀이 아이디어
이 문제는 두 가지 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] = '.';
} else {
water.push(make_pair(ny, nx));
}
water_visited[ny][nx] = 1;
}
}
swan = next_swan;
water = next_water;
day++;
}
return 0;
}풀이 흐름
- 첫 번째 백조 위치를 시작점으로 저장합니다.
- 현재 물인 위치들을 모두 water 큐에 저장합니다.
- 백조 BFS를 수행하여 현재 이동 가능한 물 영역을 모두 탐색합니다.
- 얼음에 막힌 위치는 next_swan 큐에 저장합니다.
- 물 BFS를 수행하여 현재 물과 접촉한 얼음을 녹입니다.
- 새롭게 녹은 얼음은 next_water 큐에 저장합니다.
- 현재 BFS가 끝나면 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));
}얼음이면 다음 날 탐색 대상으로 넘기고, 물이면 현재 탐색을 계속 진행하였습니다.
3. 얼음 녹이기 BFS
현재 물과 접촉한 얼음을 녹였습니다.
if (lake_map[ny][nx] == 'X') {
next_water.push(make_pair(ny, nx));
lake_map[ny][nx] = '.';
}현재 날짜에 녹는 얼음들을 다음 날 물 영역으로 사용하도록 처리하였습니다.
4. Flood Fill 방식 사용
이 문제의 핵심이었던 부분입니다.
현재 날짜에 확장 가능한 영역은 모두 탐색하고,
queue<pair<int, int>> next_swan;
queue<pair<int, int>> next_water;다음 날짜에 처리할 경계 영역만 따로 저장하였습니다.
이 방식 덕분에 매일 전체 맵을 다시 탐색하지 않고도 날짜별 확장이 가능했습니다.
5. 백조를 만나면 종료
탐색 도중 다른 백조 위치에 도달하면 현재 날짜를 출력하였습니다.
if (lake_map[curr_swan.first][curr_swan.second] == 'L') {
cout << day << '\n';
return 0;
}현재 day가 두 백조가 만날 수 있는 최소 날짜가 됩니다.
