[백준 3197] 백조의 호수 (C++)

3197번: 백조의 호수

BFS x Union Find 조합의 감탄밖에 안나오는 갓문제

문제

곳곳에 얼음이 붙어 있고 백조 두 마리가 둥등 떠 있습니다. 매일 물 공간과 접족한 모든 얼음이 매일 녹습니다. 이때 며칠이 지나야 백조들이 만날 수 있는 지 구하는 문제 입니다.

풀이

얼음은 매일마다 녹기 때문에, BFS를 돌려서 백조가 서로 만날 수 있는 길(물)이 있는지 확인하고 없으면 빙판 전체를 순회해서 얼음을 녹입니다. 이것을 여러번 돌리면 결국 언제 만나는지 구할 수 있지만, 시간 제약도 있고, 가로 세로 최대 길이가 1500이나 되기 때문에 이 방법으로는 풀 수 없습니다.

 

얼음을 녹이는 과정을 최적화 할 순 없지만, 두 백조가 만나는 것을 판별하는 알고리즘은 최적화 할 수 있을 것 같습니다. 얼음이 녹아져 있는, 그러니까 물웅덩이에 각각 라벨을 붙입니다

 

얼음을 계속 녹입니다. 얼음을 녹일 때, 녹을 예정인 칸 부분을 인접한 물웅덩이의 라벨로 수정합니다.

계속 수정하다 보면 다른 라벨 값의 물이 충돌할 때가 있는 데, 이는 두 개의 물웅덩이가 하나로 합친다는 의미로 둘 중 하나로 통일하면 됩니다.

 

Union Find (분리 집합)으로 물 웅덩이를 합치는 시뮬레이션을 구현할 수 있습니다. 두 개의 물 웅덩이가 합칠 때마다. Union 함수를 호출하여 하나로 묶습니다.

이렇게 하면 나중에 두 백조가 만날 수 있을 때 각 백조의 물 웅덩이 라벨 값의 루트 값이 일치함을 확인할 수 있게 됩니다.

int find(vector<int>& p, int x) {
    if(x != p[x]) p[x] = find(p, p[x]);
    return p[x];
}
bool union_set(vector<int>& p, int a, int b) {
    int pa = find(p, a), pb = find(p, b);
    if(pa == pb) return false;
    else {
        if(pa > pb) p[pa] = pb;
        else p[pb] = pa;
        return true;
    }
}

// 이하 생략

if(find(connected, swans[0].label) == find(connected, swans[1].label)) {
	ans = max(dp[i][j], dp[ni][nj]);
	break;
}

여기서 connected는 Union Find에서의 parents역할로 해당 라벨의 부모 라벨 값을 찾을 수 있습니다. swans[i].label은 i번째 swan이 헤엄치고 있는 물 웅덩이의 라벨 값으로 두 swan의 웅덩이가 하나로 합쳤을 때 find()함수를 사용해서 두 라벨의 최대 부모 값을 구한 다음, 이 둘이 일치하면 백조가 만날 수 있다는 뜻이 됩니다.

 

전체 코드 (C++)

#include <iostream>
#include <queue>
#include <vector>

#define INF 1999999999

using namespace std;

bool is_range(int r, int c, int i, int j) { return (0 <= i && i < r) && (0 <= j && j < c); }
int di[4] = {0,0,1,-1}, dj[4] = {1,-1,0,0};

typedef struct _Swan
{
    int i;
    int j;
    int label;
} Swan;

typedef struct _Element {
    int i;
    int j;
    int t;
} Element;

int find(vector<int>& p, int x) {
    if(x != p[x]) p[x] = find(p, p[x]);
    return p[x];
}
bool union_set(vector<int>& p, int a, int b) {
    int pa = find(p, a), pb = find(p, b);
    if(pa == pb) return false;
    else {
        if(pa > pb) p[pa] = pb;
        else p[pb] = pa;
        return true;
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    char g[1500][1500];
    int c[1500][1500], dp[1500][1500];
    int R, C, label=0, ans = INF;
    vector<int> connected;
    vector<Swan> swans;
    queue<Element> q;

    cin >> R >> C;
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            cin >> g[i][j];
    for(int i = 0; i < R; i++) {
        fill_n(c[i], C, 0);
        fill_n(dp[i], C, INF);
    }

    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            if(g[i][j] != 'X' && c[i][j] == 0) {
                c[i][j] = ++label;
                dp[i][j] = 0;
                if(g[i][j] == 'L') swans.push_back(Swan{i, j, label});
                queue<pair<int, int>> color_q;
                color_q.push({i, j});

                while(!color_q.empty()) {
                    int wall_cnt = 0;
                    int si = color_q.front().first, sj = color_q.front().second;
                    color_q.pop();
                    for(int k = 0; k < 4; k++) {
                        int ni = si + di[k], nj = sj + dj[k];
                        if(!is_range(R, C, ni, nj)) continue;
                        if(g[ni][nj] == 'X') { wall_cnt++; continue; }
                        if(c[ni][nj]) continue;
                        c[ni][nj] = label;
                        dp[ni][nj] = 0;
                        color_q.push({ni, nj});
                        if(g[ni][nj] == 'L') swans.push_back(Swan{ni, nj, label});
                    }
                    // 벽에 한번이라도 부딪힌 경우
                    if(wall_cnt) {
                        q.push(Element{si, sj, 0});
                    }
                }
            }
        }
    }
    connected = vector<int>(label+1, 0);
    for(int i = 1; i <= label; i++) connected[i] = i;
    // start
    while(!q.empty()) {
        Element u = q.front();
        int i = u.i, j = u.j;
        q.pop();
        for(int k = 0; k < 4; k++) {
            int ni = i + di[k], nj = j + dj[k];
            if(!is_range(R, C, ni, nj)) continue;
            // 육지를 만난 경우
            if(!c[ni][nj]) {
                c[ni][nj] = find(connected, c[i][j]);
                dp[ni][nj] = u.t + 1;
                q.push(Element{ni, nj, u.t + 1});
            } else {
                // 물을 만난 경우
                if(union_set(connected, c[i][j], c[ni][nj])) {
                    // 물이 합친 경우
                    if(find(connected, swans[0].label) == find(connected, swans[1].label)) {
                        ans = max(dp[i][j], dp[ni][nj]);
                        break;
                    }
                }
                
            }
        }
        if(ans < INF) break;
    }

    cout << ans << '\n';
    return 0;
}

같이 풀어보면 개꿀잼인 문제

14868번: 문명

백조의 호수와 비슷한 스타일의 문제이지만 이번엔 2개가 아닌 모든 요소가 합쳤을 때의 햇수를 구하는 문제 입니다. 특히 두 문명이 합치는 조건을 어떻게 처리해야 하는지 신중해야 합니다. 저는 이 부분에서 한참동안 생고생 하다가 겨우 풀었습니다.