Union-Find

Union-Find는 여러 개의 서로소 집합(겹치지 않는 부분집합)으로 분할된 원소들의 집합을 추적할 수 있는 데이터 구조다. 이는 서로소 집합 데이터 구조라고도 불린다.

이것이 무슨 뜻일까? 예를 들어, Union-Find 데이터 구조는 다음과 같은 집합들을 추적할 수 있다:

[ a, b, f, k ]
[ e ]
[ g, d, c ]
[ i, j ]

이 집합들은 공통된 원소가 없기 때문에 서로소 관계에 있다.

Union-Find는 세 가지 기본 연산을 지원한다:

Find(A): 원소 A가 속한 부분집합을 찾는다. 예를 들어, find(d)는 부분집합 [ g, d, c ]를 반환한다.
Union(A, B): 원소 A와 B가 속한 두 부분집합을 하나로 합친다. 예를 들어, union(d, j)는 [ g, d, c ]와 [ i, j ]를 합쳐 더 큰 집합 [ g, d, c, i, j ]를 만든다.
AddSet(A): 원소 A만을 포함하는 새로운 부분집합을 추가한다. 예를 들어, addSet(h)는 새로운 집합 [ h ]를 추가한다.

이 데이터 구조의 가장 일반적인 용도는 무방향 그래프의 연결된 컴포넌트를 추적하는 것이다. 또한 그래프의 최소 신장 트리를 찾는 크루스칼 알고리즘의 효율적인 구현에도 사용된다.

구현

Union-Find는 다양한 방식으로 구현할 수 있다. 여기서는 효율적이고 이해하기 쉬운 Weighted Quick Union 구현을 살펴본다.

참고: Union-Find의 여러 구현체가 플레이그라운드에 포함되어 있다.

public struct UnionFind<T: Hashable> {
  private var index = [T: Int]()
  private var parent = [Int]()
  private var size = [Int]()
}

Union-Find 데이터 구조는 실제로는 포레스트(forest)다. 각 부분집합은 트리로 표현된다.

여기서는 각 트리 노드의 부모만 추적하면 된다. 자식 노드는 추적할 필요가 없다. 이를 위해 parent 배열을 사용한다. parent[i]는 노드 i의 부모 인덱스를 나타낸다.

예시: parent 배열이 다음과 같다고 하자.

parent [ 1, 1, 1, 0, 2, 0, 6, 6, 6 ]
     i   0  1  2  3  4  5  6  7  8

이 경우 트리 구조는 다음과 같다.

      1              6
    /   \           / \
  0       2        7   8
 / \     /
3   5   4

이 포레스트에는 두 개의 트리가 있다. 각 트리는 하나의 부분집합에 해당한다. (참고: ASCII 아트의 한계로 인해 트리가 이진 트리로 표현되었지만, 반드시 그럴 필요는 없다.)

각 부분집합에는 고유한 번호를 부여한다. 이 번호는 해당 부분집합 트리의 루트 노드 인덱스다. 예시에서 노드 1은 첫 번째 트리의 루트이고, 노드 6은 두 번째 트리의 루트다.

따라서 이 예시에서는 두 개의 부분집합이 있다. 첫 번째는 1로, 두 번째는 6으로 레이블링된다. Find 연산은 실제로 부분집합의 내용이 아니라 이 레이블을 반환한다.

루트 노드의 parent[]는 자기 자신을 가리킨다. 즉, parent[1] = 1이고 parent[6] = 6이다. 이를 통해 어떤 노드가 루트 노드인지 알 수 있다.

집합 추가

새로운 집합을 추가하는 기본 연산의 구현부터 살펴보자.

public mutating func addSetWith(_ element: T) {
  index[element] = parent.count  // 1
  parent.append(parent.count)    // 2
  size.append(1)                 // 3
}

새로운 엘리먼트를 추가할 때, 실제로는 해당 엘리먼트만 포함하는 새로운 부분집합을 추가한다.

index 딕셔너리에 새 엘리먼트의 인덱스를 저장한다. 이를 통해 나중에 엘리먼트를 빠르게 조회할 수 있다.
그런 다음 parent 배열에 해당 인덱스를 추가하여 이 집합에 대한 새로운 트리를 구성한다. 여기서 parent[i]는 자기 자신을 가리키는데, 이는 새로운 집합을 나타내는 트리가 단 하나의 노드만 포함하고 있기 때문이다. 당연히 이 노드가 해당 트리의 루트가 된다.
size[i]는 인덱스 i에 위치한 루트 노드를 가진 트리의 노드 개수다. 새로운 집합의 경우 이 값은 1인데, 단 하나의 엘리먼트만 포함하고 있기 때문이다. 이 size 배열은 Union 연산에서 사용된다.

Find 연산

특정 엘리먼트가 포함된 집합이 이미 있는지 확인하고 싶을 때가 있다. 이때 Find 연산이 필요하다. 우리의 UnionFind 데이터 구조에서는 이 연산을 setOf() 메서드로 구현한다:

public mutating func setOf(_ element: T) -> Int? {
  if let indexOfElement = index[element] {
    return setByIndex(indexOfElement)
  } else {
    return nil
  }
}

이 메서드는 index 딕셔너리에서 엘리먼트의 인덱스를 찾은 후, 헬퍼 메서드를 사용해 해당 엘리먼트가 속한 집합을 찾는다:

private mutating func setByIndex(_ index: Int) -> Int {
  if parent[index] == index {  // 1
    return index
  } else {
    parent[index] = setByIndex(parent[index])  // 2
    return parent[index]       // 3
  }
}

트리 구조를 다루기 때문에 이 메서드는 재귀적으로 동작한다.

각 집합은 트리로 표현되며, 루트 노드의 인덱스가 집합을 식별하는 번호 역할을 한다. 우리는 찾고자 하는 엘리먼트가 속한 트리의 루트 노드를 찾아 그 인덱스를 반환한다.

먼저 주어진 인덱스가 루트 노드인지 확인한다. 즉, parent가 자신을 가리키는지 검사한다. 만약 그렇다면 작업을 종료한다.
그렇지 않으면 현재 노드의 부모에 대해 이 메서드를 재귀적으로 호출한다. 그리고 매우 중요한 작업을 수행한다: 현재 노드의 부모를 루트 노드의 인덱스로 덮어쓴다. 이렇게 하면 노드가 트리의 루트에 직접 연결된다. 다음에 이 메서드를 호출할 때는 루트까지의 경로가 훨씬 짧아지므로 더 빠르게 실행된다. 이 최적화를 하지 않으면 이 메서드의 복잡도는 **O(n)**이지만, 이제 크기 최적화(Union 섹션에서 다룸)와 함께 사용하면 거의 **O(1)**에 가까워진다.
루트 노드의 인덱스를 결과로 반환한다.

다음은 이 과정을 시각적으로 보여준다. 트리가 다음과 같다고 가정하자:

setOf(4)를 호출한다. 루트 노드를 찾기 위해 먼저 노드 2로 이동한 후 노드 7로 이동한다. (엘리먼트의 인덱스는 빨간색으로 표시됨)

setOf(4)를 호출하는 동안 트리는 다음과 같이 재구성된다:

이제 다시 setOf(4)를 호출할 때는 노드 2를 거치지 않고도 루트에 도달할 수 있다. 따라서 Union-Find 데이터 구조를 사용하면 스스로 최적화된다. 매우 멋지다!

두 엘리먼트가 같은 집합에 속하는지 확인하는 헬퍼 메서드도 있다:

public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool {
  if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {
    return firstSet == secondSet
  } else {
    return false
  }
}

이 메서드는 setOf()를 호출하므로 트리도 최적화된다.

합집합 (가중치 적용)

마지막 연산은 합집합이다. 두 집합을 하나의 더 큰 집합으로 합치는 연산이다.

    public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T) {
        if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { // 1
            if firstSet != secondSet {                // 2
                if size[firstSet] < size[secondSet] { // 3
                    parent[firstSet] = secondSet      // 4
                    size[secondSet] += size[firstSet] // 5
                } else {
                    parent[secondSet] = firstSet
                    size[firstSet] += size[secondSet]
                }
            }
        }
    }

이 코드의 동작 방식은 다음과 같다:

각 엘리먼트가 속한 집합을 찾는다. 이때 parent 배열에서 루트 노드의 인덱스인 두 정수를 얻는다.
두 집합이 동일하지 않은지 확인한다. 동일한 경우 합칠 필요가 없다.
여기서 크기 최적화(가중치 적용)가 이루어진다. 트리를 가능한 한 얕게 유지하기 위해 항상 작은 트리를 큰 트리의 루트에 붙인다. 어느 트리가 더 작은지 판단하기 위해 트리의 크기를 비교한다.
작은 트리를 큰 트리의 루트에 붙인다.
큰 트리에 노드가 추가되었으므로 그 크기를 업데이트한다.

이해를 돕기 위해 예를 들어보자. 두 개의 트리로 이루어진 집합이 있다고 가정하자:

이제 unionSetsContaining(4, and: 3)을 호출한다. 작은 트리가 큰 트리에 붙는다:

메서드 시작 부분에서 setOf()를 호출했기 때문에 큰 트리도 최적화된다. 노드 3이 이제 루트에 직접 연결된다.

최적화된 합집합 연산은 거의 O(1) 시간이 소요된다.

경로 압축(Path Compression)

private mutating func setByIndex(_ index: Int) -> Int {
    if index != parent[index] {
        // 부모 인덱스를 조회하면서 동시에 부모 인덱스를 업데이트한다.
        parent[index] = setByIndex(parent[index])
    }
    return parent[index]
}

경로 압축은 트리를 매우 평평하게 유지하도록 도와준다. 이를 통해 find 연산이 거의 **O(1)**에 가깝게 수행될 수 있다.

복잡도 요약

N개의 객체를 처리할 때

데이터 구조	합집합(Union)	찾기(Find)
Quick Find	N	1
Quick Union	트리 높이	트리 높이
Weighted Quick Union	lgN	lgN
Weighted Quick Union + 경로 압축(Path Compression)	O(1)에 매우 근접하지만 O(1)은 아님	O(1)에 매우 근접하지만 O(1)은 아님

N개의 객체에 대해 M번의 union 연산을 처리할 때

알고리즘	최악의 경우 시간 복잡도
Quick Find	M N
Quick Union	M N
Weighted Quick Union	N + M lgN
Weighted Quick Union + 경로 압축	(M + N) lgN

함께 보기

이 유용한 데이터 구조를 활용한 더 많은 예제는 플레이그라운드를 참고한다.

위키백과: Union-Find

Swift Algorithm Club을 위해 Artur Antonov가 작성, Yi Ding가 수정