Jins' Dev Inside

자료구조 Disjoint Set 을 구현하기 위한 알고리즘 혹은 Union Find 알고리즘이라 부르며, 원소들간의 집합을 분류하는 데 사용하는 자료구조이다. 흔히 Minimum Spanning Tree 를 구하는 데 있어서 핵심 자료구조로 많이 사용된다.

우리나라 말로는 서로소 집합 알고리즘 혹은 합집합 알고리즘으로 번역이 되는데, 어떤 의미로든 각 요소들에 대한 집합을 만드는 알고리즘으로 이해하면 쉽다.

주로 알고리즘 문제를 해결할 시, 일정한 기준이 주어지면 그 기준을 토대로 노드들에 대한 집합을 구성해서, 정보를 얻어내는 데 사용된다.

자료구조의 핵심적인 연산으로 Union 연산과 Find 연산이 제공된다.

Union : 두개의 집합을 합치는 연산

Find : 원소가 속한 집합을 반환하는 연산. 함수는 원소가 포함된 집합의 대푯값을 반환해야 한다.

그 외의 연산으로 MakeSet 이라는 특정한 원소를 갖는 집합을 만드는 연산이 있다.

위의 연산들을 이용해서 데이터 간의 파티션을 분류하고, 나뉘어진 파티션을 이용해 정보를 유도해내거나 최적화된 솔루션을 찾는데 이용된다.

연산은 배열 혹은 트리로 구현될 수 있다.

먼저 배열을 통해 구현할 경우 알고리즘은 다음과 같이 동작한다.

1. Find(i) : Array[i] 라는 방식으로 직접 i번째 요소의 메모리에 접근할 수 있다. i번째 요소가 대푯값을 갖고 있으면 O(1) 의 시간복잡도로 구할 수 있다.

2. Union(i, j) : i번째 요소와 j번째 요소를 합친다. 편의상 j번째 요소를 i번째 요소에 합칠 경우, 배열을 전부 순회하여 j번째 요소의 대푯값 J를 대푯값으로 갖는 요소들의 대푯값을 i번째 요소의 대푯값 I로 바꾸어준다. 

O(N) 의 시간복잡도가 생긴다.

따라서 이런 배열식 구현의 경우 N개의 요소에 대해 Union 할 경우 일반적으로 복잡도를 O(NLogN) 으로 여긴다. (각 Union 연산 시 O(N) 의 복잡도가 작업을 수행할 수록 줄어들기 때문이다.)

반면 트리로 구현할 경우, 일반적인 시간복잡도는 O(logN), 아래 기술할 경로압축까지 수행할 경우의 시간복잡도는 O( $${\displaystyle \alpha (n)}) 이 된다. 여기서  $${\displaystyle \alpha (n)} 은 극도로 빠르게 감소하는 상수에 가까운 함수이다. 

(좀 더 수학적인 자료는 다음을 참고한다. https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

트리로 구현하는 점이 코드도 더 간단하고 성능도 좋기 때문에 본 포스팅에서는 트리를 통한 구현을 설명한다.

기본적인 Union Find 알고리즘은 단순히 집합 A 와 집합 B 를 합칠 뿐이지만, Rank 를 부여하면 성능을 더 향상시킬 수 있다.

가령 다음 그림을 보자.

위의 그림처럼 순차적으로 Union 시, 자식노드로 합쳐진다면 이는 배열을 통한 구현과 다를게 없다. 트리의 높이가 높아지는 효과이기 때문에 O(N) 의 시간복잡도를 갖게 된다.

이를 방지하기 위해서는, Rank 의 개념을 도입하여, Rank 가 적은 트리를 높은 트리쪽에 합쳐주는 방법이 사용된다.

이렇게 두 트리를 합칠 때, 두 트리의 Rank 가 같을 경우에만 rank 를 증가시킴으로써, 무분별하게 tree 가 선형으로 합쳐지는 걸 방지하고 트리의 높이를 관리할 수 있다.

Rank 까지 사용하도록 구현하면 최악의 경우에도 시간복잡도가 O(logN) 이 된다.

여기서 좀 더 나아가 노드끼리 서로 합칠 때 포인터를 바로 루트 노드를 참조하도록 하는 방법이 있다. 이를 경로압축(Path Compression) 이라 하며, 최종적으로 생성된 트리는 평평한 구조가 된다.

그리고 마침내 최적화된 O( $${\displaystyle \alpha (n)}) 의 시간복잡도를 가진 알고리즘이 만들어진다.

위의 이론을 바탕으로 한 소스이다. 이론이 다소 어려울 수 있음에도 불구하고, C++로 작성된 다음 소스는 놀랍도록 단순하다.

C/C++ 에서 union 은 키워드로 관리되기 때문에, find / unite 라는 네이밍을 사용하였다. 다음은 위의 코드의 출력 결과이다.

각 집합이 Rank 에 따라 합쳐지고, 성공적으로 대푯값을 갱신하는 것을 볼 수 있다.

앞서 언급했듯이, MST를 구하기 위해 크루스칼 알고리즘이 이용하는 자료구조로도 사용되고, 다양한 값들을 대표값을 기준으로 분류하는데 은근히 많이 사용되는 알고리즘이다. 코딩 면접이나 알고리즘 공부를 한다면 알아두면 매우 유용하게 사용할 수 있다.