분리집합과 Union-Find Swift

분리집합

분리 집합은 서로 다른원소를 갖는 집합이다. 그래서 각각 분리집합의 공통원소는 없다.

전체집합 U라고 하고, 분리집합 A와 B가 있다면, 아래의 수식이 성립한다.

- U = A U B

- A ∩ B = Ø

(A와B는 U의 부분집합이다.)

 

 

Union-Find

분리집합끼리의 표현을 효율적으로 구현하고, 조작하기 위해 생긴 알고리즘이다.

서로다른 분리집합을 합치는 Union연산과 임의의 원소가 어디의 집합에 속하는지 알기위한 find연산이 주어져서 Union-Find라고 불린다.

이 알고리즘을 사용하기위해 3가지의 연산을 구현해야한다.

 

1. 초기화: 기본적으로 구현하고 조작하기위해 분리집합을 구현해야한다. 분리집합의 원소는 자기 자신을 루트노드로 갖는다.

2. Union(x,y): 두 원소 x와 y가 주어졌을때, 서로 포함하는 분리집합을 합친다.

3. Find(x): x원소의 루트노드를 찾는다. 혹은 집합을 반환한다.

 

분리집합은 기본적으로 트리형태로 구현한다. 일반적인 트리는 부모노드가 자식노드를 가리키지만 분리집합은 부모노드만 추적하면 된다.

배열을 사용하여 구현해보자.

배열을 이용해 분리집합으로 구현하면 처음엔 원소는 자기원소를 루트노드로 갖는다.(편의를 위해 0은 비우고만든다.)

parent	1	2	3	4	5	6
index	1	2	3	4	5	6

parent[index] = x 의 표현은 index라는 원소의 루트노드는 x다.

(보통 배열을 사용하면 위와 반대로 index위치에 원소가 존재한다라고 생각했는데 여기서는 index가 원소고, 위치에 있는 원소가 부모노드원소가 되는것이다.)

초기화 할때는 자기 자신이 루트노드가 되므로 모형으로 보면 다음과 같다.

 

분리집합 [1,3,5]와 [2,4,6]을 만든다.

parent	1	2	1	2	1	2
index	1	2	3	4	5	6

Union(1,3): 원소3을 원소1의 루트노드로 연결한다.

Union(1,5): 원소 5를 원소1의 루트노드로 연결한다.

이렇게 하면 원소1,3,5를 갖는 분리집합이 완성된다.

 

Find(1): 원소1의 루트노드를 출력한다. -> 원소1은 자기 자신을 루트노드를 갖고있으므로 1을 반환

Find(5): 원소5의 루트노드를 출력한다 -> 원소5는 원소1을 루트노드로 갖고있다. 1을반환

예시의 deph는 2단계라 바로 루트노드를 출력하지만, 더 깊다면 재귀호출을 통해 해당 집합의 루트노드를 반환한다.

 

두개의 분리집합을 합치는연산 Union을 사용하면 다음 그림과 같다.

parent	1	1	1	1	1	1
index	1	2	3	4	5	6

Union(1,2): 원소 1이 속한 집합과 원소2가 속한집합을 합친다.

합치는과정은 해당 루트노드가 합치려는 집합의 루트노드로 연결만 해주면된다.

합쳐졌다면 원소2,4,6 또한 루트노드 1을 가리키게 된다.

 

Union-Find의 시간복잡도는 Union연산은 연결만 해주므로 O(1)이 들지만, Find연산은 트리의 depth 만큼 재귀호출을 하므로

최소 O(1)에서 최대 O(depth)가 걸리게 된다.

 

이를 코드로 구현해보자.

import Foundation

// Union-Find
// 분리집합을 저장할 배열 parent
// parent[i] = a : i의 부모노드는 a다.
var parent = Array(repeating: 0, count: 7)

// 처음 초기화할땐 자기 자신을 루트노드로 갖는다.
for i in 1...6 {
    parent[i] = i
}

// 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
// 이때 합쳐진 집합의 루트노드는 x의 루트노드가 된다.
func union(_ x: Int, _ y: Int) {
    var rootX = find(x)
    var rootY = find(y)
    parent[rootY] = rootX
}
// 원소 x의 루트노드를 반환한다. (재귀호출)
// 재귀호출은 트리의 depth만큼 실행된다.
func find(_ x: Int) -> Int {
    if parent[x] == x { return x}
    parent[x] = find(parent[x])
    return parent[x]
}

 

 

Reference:

https://gunjoon.tistory.com/140

Disjoint Set (분리 집합)

https://victorqi.gitbooks.io/swift-algorithm/content/union-find.html

Union-Find · Swift Algorithm