서로소 집합

disjoint sets. 그래프 추상 자료형. union 연산과 find 연산을 쓰기 때문에 union-find 자료구조라고도 한다.

연산

• union: 두 오브젝트를 연결함.
• find: 두 오브젝트가 연결 되었는지 질의함.

union, 즉 연결에 대한 합의가 있어야 한다. 따라서 연결을 다음과 같이 정의한다.

오브젝트 $p$가 다른 오브젝트 $p$에 연결되었음을 $p\rightarrow p$라고 하자.

• 반사적(reflexive)¹: $p \rightarrow p$ 모든 객체는 자기 자신과 연결되어있다.
• 대칭적(symmetric): $p \rightarrow q$이면 $q \rightarrow p$이다. 연결은 양방향이다.
• 추이적(transitive): $p \rightarrow q$이고 $q \rightarrow r$이면 $p \rightarrow r$이다.

연결되어 있는 가장 커다란 집합을 연결 요소(connected component)라고 부른다. 아래의 그림에서는 0은 {0} 그 자체, 1, 4는 서로 연결되어 있으므로 {1, 4}, 2, 3도 마찬가지로 {2, 3}이 연결 요소라고 볼 수 있다. 연결 요소를 이용하면 find 연산을 오브젝트끼리 연결 되어있는지 확인하는 문제에서 하나의 연결 요소에 포함되어있는지 확인하는 문제로 바꿀 수 있다.

 0 1 2-3
   | 
   4

구현

Quick Find

find 연산이 빠른 구현이다.

선형 리스트를 이용하여 간단히 구현할 수 있다. 아래의 서로소 집합을 예로 보자:

0  1--2  3--4
|     |  |  |
5--6  7  8  9

이를 선형 리스트로 나타내면 아래와 같다. 각각의 원소를 인덱스로, 리스트의 값을 연결 요소의 id로 표현한다. 같은 연결 요소에 있다면 같은 리스트 값을 가진다:

index     0   1   2   3   4   5   6   7   8   9  
        +---+---+---+---+---+---+---+---+---+---+
content | 0 | 1 | 1 | 8 | 8 | 0 | 0 | 1 | 8 | 8 |
        +---+---+---+---+---+---+---+---+---+---+

0, 5, 6은 같은 연결 요소에 있기 때문에 해당 인덱스의 리스트 값이 같다.

find 구현은 쉽다. $p$와 $q$의 연결 요소가 같은지 확인하면 된다.

union는 조금 번거롭다. 연결 할 때 같은 연결 요소의 원소 수만큼 그 내용을 바꾸어주어야 한다. 위의 그림에서 0번 연결 요소({0, 5, 6})과 8번 연결 요소({3, 4, 8, 9})를 union한다고 생각해보자. 0번의 원소를 8로 바꾸거나 8번의 원소를 0으로 바꾸어주어야한다. 연결 요소 $C$의 원소를 별도로 저장하지 않는다면 배열 전체를 순회하며 확인해야한다.