문제

백조의 호수 성공다국어

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 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'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

풀이

탐색문제이다.

격자가 1500 * 1500이고 물과 닿아있는 얼음이 한 사이클에 한칸씩 녹기 때문에 단순히 연결될 때 까지 얼음을 녹이고 탐색을 하게된다면 시간초과가 나게된다.

처음에 생각했던 방법은 union-find 로 얼음이 녹을때 마다 merge 하는 과정을 해서 두마리의 백조의 root가 같아지는 부분을 체크하면 되겠다고 생각했다.

path-optimization을 사용해서 유니온파인드를 진행한다면 find 과정이 거의 상수시간이 되기 때문에 R*C * 상수 의 연산횟수로 계산을 하여 시간은 문제가 없다고 생각했다.

하지만 생각한대로 잘 풀리지 않아서 그냥 BFS로 진행했다.

어쨌는 물과 닿아있는 얼음이 녹는 것이기때문에 모든 물에 대해 탐색하고, 그 과정에서 물과 닿아있는 얼음을 체크해 다음 물에대한 BFS 과정의 인수로 넣어주었다.

그리고 각각의 과정에서 백조가 갈 수 있는 부분도 탐색하고, 얼음이 녹는다면 추가로 갈 수 있는 부분을 다음 백조에 대한 BFS과정의 인수로 넣어주었다.

단순계산했을때 한번 방문한 노드에 대해 추가 방문을 하지 않고, 한번에 얼음에 대한 과정이 물에 대한 BFS, 백조에 대한 BFS이므로

2*R*C의 시간으로 계산을 했다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <deque>
#define INTMAX 987654321
using namespace std;
int R, C, check;
string board[1501];
int ans = 0, dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1}, vis[1501][1501];
queue<pair<int,int > > q, q2, sq, sq2;
int main() {
    cin>>R>>C;
    for(int i=0; i<R; i++){
        cin>>board[i];
    }
    for(int i=0; i<R; i++)
        for(int j=0; j<C; j++) {
            if(board[i][j] == '.' || board[i][j] == 'L'){
                q2.push(make_pair(i, j));
            }
            if(board[i][j] == 'L'){
                if(sq2.empty()){
                    sq2.push(make_pair(i, j));
                    vis[i][j] = 1;
                }
            }
        }
        while(!check) {
            while(!q2.empty()){
                q.push(q2.front()); q2.pop();
            }
            while(!sq2.empty()){
                sq.push(sq2.front()); sq2.pop();
            }
            while(!sq.empty() && !check) {
                auto cur = sq.front(); sq.pop();
                for(int i=0; i<4; i++) {
                    int nx = cur.first + dx[i];
                    int ny = cur.second + dy[i];
                    if(nx<0||nx>=R||ny<0||ny>=C) continue;
                    if(vis[nx][ny]) continue;
                    if(board[nx][ny]=='.'){
                        sq.push(make_pair(nx, ny));
                        vis[nx][ny] = 1;
                    }
                    if(board[nx][ny] == 'X'){
                        sq2.push(make_pair(nx, ny));
                        vis[nx][ny] = 1;
                    }
                    if(board[nx][ny] == 'L') {
                        check = 1;
                        break;
                    }
                }
            }
            if(check){
                cout<<ans;
                break;
            }
            while(!q.empty() && !check) {
                auto cur = q.front(); q.pop();
                for(int i=0; i<4; i++) {
                    int nx = cur.first + dx[i];
                    int ny = cur.second + dy[i];
                    if(nx<0||nx>=R||ny<0||ny>=C) continue;
                    if(board[nx][ny] == 'X'){
                        q2.push(make_pair(nx, ny));
                        board[nx][ny] = '.';
                    }
                }
            }
            ans+=1;
        }
}