Disjoint Set & Union-Find

목차

• Disjoint Set (서로소 집합, 분리 집합)
  - Time Complexity
• 구현
  - MakeSet(n)
  - find(x)
  - union(x, y)
• 최적화
  - Path Compression
  - Path Halving
  - Path Splitting
  - Union by Rank
  - Union by Size
  
  

---

Disjoint Set (서로소 집합, 분리 집합)

원소들의 모임을 표현하는 자료구조로, 각각의 집합은 공통된 원소가 없다.

주로 서로 다른 원소들이 동일한 집합에 속하는지 여부를 판별하는데 사용된다.

 

Time Complexity

경로 압축과 트리 깊이 제어를 하는 로직이 없다면 선형 구조와 같은 예시에서 하나의 작업이 최대 O(N)이 될 수 있다.

하지만, 최적화를 위한 로직을 적용했다면, O(α(N)) <= O(4) 라고 한다.

---

구현

MakeSet(x)

원소 x를 자기 자신을 원소로 가지는 집합으로 만든다.
parent 배열에 원소 x가 속한 집합의 대표 원소를 지정해주는 과정이다.

원소들의 관계에 대한 정보가 주어지지 않은 상태라면, 모든 원소는 자기 자신을 집합으로 초기화 해주어야 한다.

때문에 makeSet 메서드는 대신 아래와 같이 초기화를 진행해주자.

parent 배열의 모든 요소에 자신의 인덱스와 동일한 번호로 초기화 해주어, 자기 자신을 집합으로 표현할 수 있다.

---

find(x)

원소 x가 속한 집합의 대표 원소를 반환한다.

x가 만약 자신이 속한 집합의 대표 원소( parent[x] )일 때 x를 반환하고, 아닌 경우에는 parent[x]에 대해 대표 원소와 동일할 때 까지 탐색을 시도해야 한다.

---

union(x, y)

원소 x와 y가 속한 두 집합을 하나로 합친다.

두 집합에 대해 각각의 대표 원소가 다르다면, 두 집합은 서로 다른 집합이기 때문에 합쳐주어 공통된 대표 원소로 새로 갱신해주어야 한다.

 

여기까지가 기본적인 DisjointSet & Union-Find에 대한 구현이다.

---

최적화

Path Compression

기존의 find(x)의 작동방식에 대해 기억나는가?

1. 원소 x가 대표 원소이면 반환.
2. 아니라면 대표 원소에 대해 재탐색

이러한 과정은 이미 하나의 집합으로 합쳐진 원소에 대해서 자신이 속한 대표 원소를 찾는 과정이 최악의 경우 O(N)이라는 사실이다.

선형구조로 연결된 집합에 대해서 생각해보자.

union(4, 3)
union(3, 2)
union(2, 1)

>>> parent : [0, 1, 1, 2, 3, ... ]

원소 1, 2, 3, 4는 분명 하나의 집합이다.

하나의 집합에는 하나의 대표 원소만 존재해야 하지만, 위의 과정을 보면 다음과 같은 탐색 과정이 발생한다.

find(4) = find(3) = find(2) = 1
find(3) = find(2) = 1
find(2) = 1
find(1) = 1

즉, 하나의 집합 내 모든 원소들에 대해 대표 원소를 갱신하여, 불필요한 재탐색을 방지하고, 집합의 대표 원소를 명확히 해줄 필요가 있다.

find를 호출할 때마다 경로에 있는 모든 원소들의 대표 원소를 설정해주자.

---

Path Halving

원소 x가 대표 원소가 아닐 때, 대표 원소에 대한 대표 원소를 즉각 확인하는 방법이다.

즉, 경로 압축이 되지 않은 집합에 대해 두개씩 건너뛰며 확인하는 방법이다.

---

Path Splitting

Path Halving와 비슷하지만, 대표 원소는 두개씩 건너뛰며 갱신해주지만, 다음 탐색대상은 순차적으로 증가하는 방법이다.

 

보통은 Path Compression 방식을 자주 사용하지만, 선형 구조의 집합과 같은 예외적인 경우에는 Path Halving/Splitting 방식이 더 좋은 경우도 있다.

 

 

다음으로는 union을 최적화하는 방법에 대해 알아보자.

이번 글을 작성하며 필자 또한 새롭게 알게된 최적화 방식이다.

처음에 작성한 union 코드를 살펴보자.

 

이러한 방식은 union하고자 하는 두 집합에 원소의 개수가 더 많은 집합의 대표 원소를 바꾸게 되는 일이 발생할 수 있다.

 

아래의 표를 살펴보자.

두 집합 {1, 2, 3}, {4, 5, 6, ... , 12, 13}에 대해 union(4, 3)하는 경우를 생각해 보자.

필자가 사용한 방법대로라면 두 번째 집합의 대표 원소를 모두 1로 바꿔야한다.

첫 번째 집합의 대표 원소를 4로 바꾸는 방법이 좀 더 효율적이다.

 

위와 같이 집합의 구성에 따라 어떻게 최적화 할 수 있는지 알아보자.

 

 

Union by Rank

집합으로 이루어진 트리의 깊이를 비교하여 깊이가 낮은 집합의 대표 원소를 큰 집합의 대표원소로 갱신한다.

이를 위해서 집합에 대한 깊이를 저장할 rank 배열이 필요하다.

union하는 두 집합의 rank에 저장된 트리의 깊이를 비교해 더 작은 쪽의 대표 원소를 바꿔주면 된다.

---

 

Union by Size

이번에는 트리의 깊이가 아닌, 집합의 크기로 비교하는 방법이다.

집합의 크기를 저장할 size 배열을 선언해주자.

자기 자신에 대한 크기인 1로 초기화 해야한다.

마찬가지로 대소비교에 따라 더 작은 쪽을 큰 쪽으로 붙여주면 된다.

---

소스코드

소스코드 보기

---

출처

Disjoint-set data structure - Wikipedia