Disjoint Set Union

Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다.

서로 다른 원소들이 같은 집합에 속해있는지 판별하는데 쓰인다.

이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다.

Disjoint Set 사이에는 교집합이 없기 때문에(정의로 인해), 서로간을 합해주는 연산으로 집합이 합쳐지는 과정이 있을 수 있다. 합하는 과정을 매우 빠르게, 그리고 원소를 판별하는 과정또한 매우 빠르게 하기 위해서 DSU를 사용한다.

먼저, Disjoint Set는 트리를 이용하여 표현하는데, 같은 집합에 속한 원소들 중 하나를 루트로 하고, 나머지 원소들을 각각 루트 원소의 자식이 되도록 표현하는 것이다.

트리를 구성하는 과정에서는 자식 노드만 부모노드를 알고 있으면 된다. 같은 집합인지 확인하는 과정을 그 원소가 속해있는 트리의 루트원소가 무엇인가를 통하여 판별하기 때문이다. (같은 트리에 속한 원소들의 루트는 다 같으며, 원소의 루트가 다를 경우 다른 트리임이 분명하다.)

위와 같이 트리로 표현한 이후, 비교할 원소들에서 부모를 찾아가면서 루트를 찾고, 원소들의 루트가 같은지를 이용하여 서로 같은 집합인지를 판별할 수 있다.

Union

위와 같이 표현한 두 집합(트리)를 합치는 과정을 구현하는 것은, 두 트리 중 하나의 루트를 다른 한 트리의 자식으로 만드는 것이다. 이 경우, 자식으로 합쳐진 트리의 새로운 루트는 자식으로 합쳐지지 않은 다른 트리의 루트임을 알 수 있다. 즉, 두 트리의 합 트리의 모든 원소들의 루트는 합 트리의 루트와 같다는 것을 알 수 있고, 이는 두 집합이 합쳐진 것과 같음을 알 수 있다.

집합을 트리로 구현하여 표현하면 분리집합을 판별할 수 있고, 이를 합하는 과정 또한 해결할 수 있다. 하지만 이처럼만 판별하면 문제가 생기는데, 바로 트리 내에서 원소들의 편중이 일어날 수 있다는 것이다. 최악의 경우, 선형 트리가 만들어져 한 번 루트를 찾을 때에 O(트리의 크기) 만큼의 시간이 걸릴 수 있다.

Sparse Table을 이용하면 루트를 O(lgN) (N : 트리의 크기) 만큼에 찾을 수 있지만, DSU에서 Sparse Table은 사용하지 않는다. DSU에서는 처음 집합을 구현하는 것 뿐만 아니라 집합의 합연산까지 해야하기 때문이다. (집합을 합치는 과정에서 Sparse Table을 다시 구축해야 하고, 이과정은 구현하기 상당히 어렵다.)

DSU를 구현할 때에, 루트를 찾는 과정은 앞서 언급한 것과 같이 부모를 향해가면서 찾을 것이다. 즉, DSU의 속도를 향상시키기 위해 구현하는 방법에서의 향상을 고려할 수 있다.

1. 경로 압축 (Path Compression)

Path Compression은 집합 내 한 원소에서 루트를 찾는 과정을 압축시키는 방법이다. 원소에서 부모를 향해가면서 원소와 루트 사이의 모든 원소들을 방문한다. 이 과정에서 원소와 루트 사이에 방문한 모든 원소들의 루트 또한 현 원소에서의 루트와 같다는 것을 알 수 있다. 결국, 한 경로를 찾아가는 과정에서 방문한 모든 원소의 부모를 루트로 갱신해준다. 이를 통해서 경로에 존재하는 모든 원소의 부모가 바로 루트로 이어지게 만들 수 있다.

2. 랭크 압축 (Rank Compression)

Rank Compression은 합하는 과정을 향상시키므로 이후 한 원소에서 루트를 찾아가는 경로 자체를 줄일 수 있는 방법이다. 우선, 합치는 과정에서 한 트리의 루트를 다른 트리의 루트의 자식으로만 합한다, 이 과정에서 불필요한 경로를 단축할 수 있다. 그리고 더 중요한 압축 방법이 있는데, 많이 사용되는 방법은 두 가지가 있다.

1. 트리의 깊이가 더 작은 쪽을 큰 쪽에 합한다.

2. 트리의 크기가 더 작은 쪽을 큰 쪽에 합한다.

1번의 경우, 깊이가 더 작은 쪽을 큰 쪽에 합하는 것으로, 두 트리를 합치면서 깊이가 깊어지는 상황에는 깊이가 1 증가하고, 그 과정에서 합한 트리의 크기는 2배 증가하기 때문이다. (Rank Compression을 생각해보면, 가장 깊은 부분의 구조는 완전 이진트리에 가깝다는 것을 알 수 있다.) 즉, 최악의 경우 이진트리와 같이 구현된다면, 그 경우 깊이는 완전이진트리의 깊이와 비슷한 lgN정도가 된다.

최악의 깊이 증가가 있기 위해서는 같은 깊이의 최소 크기 트리가 필요하다. - 깊은 부분은 완전 이진트리에 가까워진다.

때문에 최악의 경우, 경로의 길이는 lgN 정도임을 알 수 있다. 이를 통해 쿼리당 처리 속도 O(lgN)이 보장된다.

이를 경로 압축과 함께 사용할 경우, 현 트리의 깊이를 정확히 알기는 어려운데, 이는 압축되기 이전의 깊이를 이용하여도 크게 문제는 없다. (압축된 깊이) <= (압축 이전의 깊이)를 만족하기 때문에, 어떤 경우에도 O(lgN)보다 느려지는 경우는 없다.

2번의 경우, 정확히 설명하기는 어려우나, 1번과 비슷하거나 더 좋은 성능을 낸다. 이를 구현하는 과정에서 '크기가 작은 쪽의 깊이가 작을 가능성이 높다'는 것과 최악으로 합쳐지는 경우를 생각하면, 현재 크기의 트리를 구성하는 트리도 최악에 완전 이진트리에 가까워짐을 알 수 있고, 보통의 경우 성능은 더 좋음을 알 수 있다. 이를 통해 최악에 깊이가 lgN에 비슷해진다는 것을 알 수 있고, 1번과 같은 성능이 보장된다. (1번은 진행할수록 처음에 정해둔 깊이와 실제 깊이간의 차이가 커져 최악의 경우 속도는 같지만, 평균적인 경우 크기를 기준으로 한 압축의 성능이 좋다.)

보통 프로그래밍을 하는 과정에서, Rank Compression을 사용하지 않는 경우도 흔하다. 이유는 Path Compression 단계에서 사용한 경로 내에 있는 원소들은 새로 참조할 경우 O(1)이 보장된다는 그 사실 자체가 매우 강하기 때문이다. 보통의 경우 Rank Compression을 사용하지 않아도 크게 문제가 되지는 않지만...Rank Compression을 이용하지 않고 Path Compression만 이용한 DSU를 저격하는 데이터를 만들 경우 최악에 O(NlgN)에 동작하도록 만들 수 있다. 

3. Path Compression + Rank Compression

Path Compression과 Rank Compression을 둘 다 이용할 경우, DSU의 시간복잡도는 O(α(N))이다. α(N)은 에커먼 함수의 역함수인데, 거의 상수에 가깝게 동작한다고 볼 수 있다. 에커먼 함수의 계산량에 관련된 정보는 링크를 걸어두도록 하겠다.

Rank Compression을 사용하지 않을 경우, 랜덤한 데이터에서는 언급한 시간복잡도와 비슷한 정도의 성능이 나오니, 일반적인 경우의 구현은 Path Compression만 이용해도 괜찮을 것이다. (하지만 Path Compression을 통한 압축을 하면 안되는 경우, Rank Compression만을 이용한 시간의 향상이 필요한 경우도 있으니 알아두면 좋다.)

에커먼 함수

4. 집합의 분리

DSU를 통하여 집합을 합할 수 있다면, 집합을 분리하는 경우가 있지 않을까 생각할 수 있다. 하지만, Online으로 분리해야 하는 집합을 받는다면, 이를 효율적으로 Disjoint Set에서 분리해내는 것은 매우매우 어렵다.

Offline 쿼리로 들어올 경우, 이를 O(Qlg^2Q)(Q : 쿼리 수)에 해결하는 방법이 존재한다. 링크를 건 블로그에서 소개하는 방법은 Rank Compression을 이용한 분할정복 풀이이다. 정말 좋은 풀이니 궁금하면 참고하길 바란다. 

Offline solution of Dynamic Connectivity Problem