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;
}