3197번: 백조의 호수 (BOJ C/C++)
3197번: 백조의 호수
사용 언어: C++
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
풀이
문제를 보고 처음에 생각난 풀이는 2146번: 다리 만들기와 유사하겠다 생각해서 코드를 작성하다가 든 생각 : '아 이건 아니겠구나'. 1500x1500 보드에 그 많은 바다 부분에 전부 BFS를 돌리려고 하면 코드가 너무 복잡하고 시간 초과가 뜨겠단 생각에 접었다.
1. 물과 인접한 얼음은 다음 날 물이 되므로 nextQ에 물이 될 얼음을 임시로 저장했다가 그 위치를 다시 Q에 넣어서 녹을 얼음의 위치에서 다음 BFS를 시작한다.
2. 백조의 BFS인 LQ도 마찬가지로 만날 얼음을 임시로 저장할 nextLQ를 사용한다. 추가로 백조의 BFS에서 이미 방문한 물은 무시해도 된다. 못 만났을 경우 빙판 때문에 못 만나므로 빙판이 녹으면서 생기는 물의 위치를 저장했다가 주면 되기 때문이다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define MAX 1502
string board[MAX];
bool visited[MAX][MAX];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int R, C, ans, lx, ly;
queue<pair<int,int>> Q; //바다, 백조 저장할 큐
queue<pair<int,int>> nextQ; //녹은 얼음의 좌표를 저장 -> 이후 녹일 얼음을 찾는 물의 시작 좌표
queue<pair<int,int>> LQ; //백조 저장할 큐
queue<pair<int,int>> nextLQ; //(lx,ly)에서 출발해서 녹은 얼음의 좌표 저장 -> 이후 nextLQ에 저장
bool OOB(int a, int b){
return a<0 || a>=R || b<0 || b>=C;
}
void bfs(){
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(board[i][j] == 'L'){
lx = i;
ly = j;
}
if(board[i][j] != 'X')
Q.push({i,j}); //바다 and 백조 저장
}
}
//백조 한마리만 저장
LQ.push({lx,ly});
visited[lx][ly] = 1;
while(1){
while (!Q.empty()){ //얼음 녹이기 BFS
auto cur = Q.front(); Q.pop();
for (int dir=0; dir<4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (OOB(nx,ny)) continue;
if (visited[nx][ny]) continue;
//(녹은 얼음==물)의 옆의 얼음 -> nextQ에 넣기
if (board[nx][ny] == 'X'){
board[nx][ny] = '.';
nextQ.push({nx, ny});
}
}
}
//전에 녹은 얼음을 Q에 넣어 Q가 다시 주변 얼음 (cur.X,cur.Y)로 시작
while (!nextQ.empty()){
auto cur = nextQ.front(); nextQ.pop();
Q.push({cur.X, cur.Y});
}
//하루 지나감
ans++;
//한 백조의 위치 (lx,ly)에서 출발한 BFS LQ -> 다른 백조 찾기
while (!LQ.empty()){
auto cur = LQ.front(); LQ.pop();
for (int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(OOB(nx,ny)) continue;
if(visited[nx][ny]) continue;
if(board[nx][ny] == '.'){
visited[nx][ny] = 1;
LQ.push({nx, ny});
}
else if(board[nx][ny] == 'X'){
nextLQ.push({cur.X, cur.Y});
}
else if(board[nx][ny] == 'L'){
return;
}
}
}
//임시로 기억한 백조가 녹인 얼음 nextLQ에서 처리
while(!nextLQ.empty()){
auto cur = nextLQ.front(); nextLQ.pop();
LQ.push({cur.X, cur.Y});
visited[cur.X][cur.Y] = 1;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for(int i=0; i<R; i++) cin >> board[i];
bfs();
cout << ans << '\n';
return 0;
}