활용의 미학 : Union-Find + BFS 짬뽕 (BOJ 3197 백조의 호수)

처음 Union-Find 자료구조를 공부했을땐, 이게 단독으로 어디에 쓰일까 의문이 들었다.

하지만, 이 문제를 고생해서 풀고 나니, Union-Find가 보이는 강점을 알게 된 것 같다.

 

[문제 설명]

백조의 호수의 world는 호수와 빙판으로 이루어져 있고, 두 마리의 백조가 호수 위에 살고 있다.

호수와 인접한 빙판은 하루가 지날때마다 한 칸씩 녹으며,

우리는 두 마리 백조가 살고 있는 호수가 합쳐질때까지 시간이 얼마나 걸리는지 알고싶어한다.

 

[풀이]

문제의 핵심 구현 포인트는 다음 두 가지가 있다.

 

1. 호수와 인접한 빙판만 하루에 한 칸씩 녹이기

    → BFS

2. 서로 맞닿은 호수를 하나로 합치는 방법

    → Union-Find

 

시뮬레이션에서의 일반적인 BFS는 자체 Queue를 사용하며, 시작 지점으로부터 마름모꼴로 퍼져나가며 탐색한다.  

매 다음 탐색할 위치를 큐에 넣는 방식으로 탐색을 지속해나간다.

 

하지만 이 문제에서 우리는 BFS 탐색 방법을 사용하되, 자동으로 탐색이 지속되는 부분은 바꿔서 활용한다.

또, 호수를 합칠때는 Union-Find로 간결하게 구현한다.

 

[놓친 부분]

주의 1. 백조가 있지 않은 빈 호수라고 무시하면 안된다. 빈 호수 주변의 빙판도 녹여줘야 한다.

주의 2. BFS에 의한 중복 탐색을 줄이지 못하면 TLE가 뜬다.

---

Sol 1) 백조A 에서 백조B까지의 최단거리 중, 뚫린 벽이 가장 적은 최단거리 구하기

→ (실패) 최단거리 바깥에 있는 빈 호수에 의해 벽이 더 빨리 뚫리는 반례가 존재. (주의 1 참고)

---

Sol 2) 하루에 백조1, 백조2, 그리고 빈 호수들의 각 포인트들에서 돌아가며 BFS 차례로 진행.

- BFS하는 동시에 union 처리;

int root[1501][1501] 배열을 만들어서, 백조1이 있는 호수는 1, 백조2가 있는 호수는 2, 일반 호수는 3으로 표시하고, 

BFS에 의해 주변 칸들이 탐색될 때, 서로 root 비교해서 더 낮은 값으로 바꾸기 (즉, 백조 중심으로 합치기)

 

- set을 사용해서, union되어 사라진 시작 지점은 set에서 제거하는식으로 유효한 시작 지점만 남김

 

→ (실패; TLE) 답은 잘 찾으나, 매번 같은 시작 지점에서 BFS를 돌려대서 이미 탐색한 곳을 몇 번이고 계속 중복 탐색함. TLE. (주의 2 참고)

 

---

Sol 3) (성공) Sol 2 의 중복 탐색 문제 해결 + Union-Find 자료구조 제대로 사용해서 호수 합치기 구현

- Queue 활용; 시작 지점이 될만한 좌표를 모두 Queue에 넣고 뺄때마다 BFS.

BFS에 시작 지점만 인수로 넣어주면, 자동으로 주변 값들을 Queue에 넣어가며 탐색하던 기능을 BFS 밖으로 빼버림.

 

- BFS 탐색 극히 제한; 기존엔 상하좌우 좌표에서 이미 visited 된게 아니라면 다 queue에 넣었지만, 이젠 빙하 만날때만 Queue에 넣기 (빙하가 녹아서 호수가 됬으므로, 다음에 탐색하겠다는 의미).

대신, 이제 BFS가 주변 탐색을 안하므로, 탐색할 위치들을 처음 world input 받아들일때 Queue에다가 다 넣어줘야함.

 

- Queue에서 뽑은 시작 지점이 빙하가 아닌 그냥 호수라면, Union-Find 자료구조를 사용해서 주변 호수를 합침.

여기서, 두 호수가 서로 같은지 다른지만 판단하면 되므로 어떻게 합쳐지든 관심 없음.

* Union-Find 자료구조에선, Indexing 때문에 Sol 2에서 처럼 우리가 정한 임의의 값(1또는 2) 으로 합칠 수가 없었음.   

 

→ 최대 1500x1500의 맵 전체 한번만 탐색 + Union 최대 1500x1500번 + 하루가 끝날때마다 Find < 1초

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
using tup = tuple<int, int, int>;

#define X first
#define Y second

const int INF = int(1e9);
const int MAXN = 1501;
int world[MAXN][MAXN];
int visited[MAXN][MAXN];
vi parent(1500*1500);

int N, M;

int Find (int x) {
    return x == parent[x] ? x : parent[x] = Find(parent[x]);
}

/*
그냥 한 그룹으로 합쳐진다는게 중요.
*/
void Unions(int a, int b) {
    a = Find(a), b = Find(b);
    a < b ? parent[b] = a : parent[a] = b;
};

int main() {
#ifdef DBG
    freopen("input.txt", "r", stdin);
#endif
    fastio;
    queue<int> swans;
    deque<int> lakes;

    auto to_pos = [&](int x, int y) { return (x - 1) * M + (y - 1);};
    auto pos_X = [&](int pos) { return pos/M + 1;};
    auto pos_Y = [&](int pos) { return pos % M + 1;};

    scanf("%d%d", &N, &M);
    iota(parent.begin(), parent.begin()+N*M, 0);
    char tmp;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf(" %c", &tmp);
            if (tmp == 'X') {
                world[i][j] = 1;
                continue;
            }
            else if (tmp == 'L') {
                swans.push(to_pos(i, j));
            }
            else
                lakes.push_back(to_pos(i, j));

            world[i][j] = 0;
        }
    }

    int swan1 = swans.front(); swans.pop();
    int swan2 = swans.front(); swans.pop();
    lakes.push_front(swan1); 
    lakes.push_front(swan2);

    auto boundary = [&](int x, int y) {return 0 < x && x <= N && 0 < y && y <= M;};
    int x, y, day = 0;
    do {
        int cnt = lakes.size(); // Separates each day's work for single queue

        // Perform BFS for each starting point from the queue
        while (cnt--) {
            int lake = lakes.front(); lakes.pop_front();
            x = pos_X(lake); y = pos_Y(lake);

            visited[x][y] = 0; // ★ 녹아서 일반 호수가 된 (x,y) visited 초기화 해주기 (안해주면 union 안함)

            // Limited BFS (only merge for normal lake, put into queue only for melting ice)
            for (int i = 0; i < 4; i++) {
                int xn = x + "1210"[i] - '1'; // E S W N
                int yn = y + "2101"[i] - '1';

                // Boundary & visited check
                if (!boundary(xn, yn) || visited[xn][yn])
                    continue;

                // visited[xn][yn] = 1; 
                /*
                ★★
                Q. BFS에서 visited 처리를 왜 해주지?
                중복해서 큐에 넣지 않으려고 해주는거잖아. 근데 우리는 일반 호수는 큐에 안넣고 union만 해주므로, visited 처리 안해줘도 됨.
                오히려, 지금 산발적으로 BFS가 일어나므로, 일반 호수의 visited 처리로 인해 두 호수가 서로 union이 안되는 경우 생길 수 있음. 
                따라서, 벽이 아닌 일반 호수는 오히려 visited 처리 안해줘서, union 될 수 있도록 한다.
                */

                // Melt & Stop
                if (world[xn][yn] == 1) {
                    world[xn][yn] = 0;
                    lakes.push_back(to_pos(xn, yn));
                    visited[xn][yn] = 1; // ★ 녹인 벽은 큐에 넣어야 하므로, 한번 녹인 벽은 visited 처리로 중복 삽입 방지
                }
                // Merge lakes together
                else {
                    Unions(to_pos(x, y), to_pos(xn, yn));
                    /*
                    ★★★
                    이렇게 하다보면 언젠간 호수 전체가 하나로 묶이게 될 것.
                    어떻게 묶이던지는 상관없음; swan1과 swan2가 같은 묶음에 있는지 없는지만 확인하면 되니.
                    */
                }
            }
        }

        if (Find(swan1) == Find(swan2))
             break;

        day++;
    }while (!lakes.empty());

    printf("%d", day);

    return 0;
}

---

여기서 배워가는 점? 

 

- Graph가 격자로 주어지는 Simulation 식 문제에서 Union-Find를 활용하는 법 

vi parent (1500*1500, 0)

vi parent (1500*1500)

...

// BFS 내부
for (int i = 0; i < 4; i++) {
	...
    
	Unions(to_pos(x, y), to_pos(xn, yn)); // 시작 지점과 상하좌우 지점을 각각 합쳐 
}

- BFS를 자유자재로 다루는 법 (visited 처리 조절, queue 밖으로 빼기