✏️

[JS] Disjoint Set의 표현: Union-Find


Disjoint Set

'Disjoint set'는 공통 원소가 없는 부분 집합들이다.

어떤 교양 대면 수업에 여러 학과 사람들이 모여있다고 해보자. 이때 교수님이 갑자기 같은 과 사람들끼리 조를 만들라고 한다. 그럼 학생들은 이리 저리 돌아다니다가 같은 과 사람을 찾으면 팀을 이뤄 같이 움직이게 될 것이다. 그리고 팀끼리도 같은 과인 것을 확인하면 두 팀은 합쳐진다. 만들어진 조들은 공통 원소가 없는 부분 집합들, disjoint set 이 된다.

이 상황을 자료구조로 표현한 것이, 즉, disjoint set에 대한 정보를 저장하고 조작하는 자료 구조가 'Union-Find'다.

트리를 이용한 Union-Find

Union-Find를 구현하기 위해서는 세 가지 연산이 필요하다.

  • 초기화: n개의 원소가 각각의 집합에 포함되어 있도록 초기화한다.

  • 합치기(union) 연산: 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.

  • 찾기(find) 연산: 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환한다.

Union-Find 는 주로 트리 자료구조를 사용해서 한 집합에 속하는 원소들을 하나의 트리로 묶어준다.

구현하기

각 원소가 포함된 트리의 루트를 찾은 뒤, 이들이 같은지 비교해서 두 원소가 같은 트리에 속해 있는지 확인할 수 있다. 이런 find 연산을 구현하기 위해서는 모든 자식 노드가 부모에 대한 정보를 가지고 있어야 한다. 반면, 부모는 자식으로 내려갈 필요가 없기 때문에 부모는 자식에 대한 정보를 가지고 있을 필요가 없다. 루트는 부모가 없기 떄문에 보통 자기 자신을 가리키게 구현한다.

트리로 집합 표현을 하면 union 연산이 굉장히 쉽다. 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣어주면 된다.

1class NaiveDisjointSet {
2 /**
3 * @param {number} n The number of elements
4 */
5 constructor(n) {
6 this.parent = new Array(n).fill(0).map((_, i) => i);
7 }
8 /**
9 * @param u
10 * @return {number} The root node
11 */
12 find(u) {
13 if (u === this.parent[u]) return u;
14 return this.find(this.parent[u]);
15 }
16 /**
17 * @param {number} u Element 1
18 * @param {number} v Element 2
19 */
20 merge(u, v) {
21 let u_root = this.find(u);
22 let v_root = this.find(v);
23
24 if (u_root === v_root) return;
25
26 this.parent[u] = v;
27 }
28}

최적화하기

트리를 사용하면 연산의 순서에 따라 잘못하면 트리가 한쪽에 치우쳐질 수 있다는 문제를 피할 수 없다. 이 문제를 해결하기 위해 트리를 합칠 때 항상 '높이가 더 낮은 트리'를 '높이가 더 높은 트리' 밑에 집어넣음으로써 트리가 치우쳐지는 상황을 방지한다. 이 최적화를 랭크에 의한 합치기(union-by-rank) 최적화라고 한다.

1class DisjointSet {
2 /**
3 * @param {number} n The number of elements
4 */
5 constructor(n) {
6 this.parent = new Array(n).fill(0).map((_, i) => i);
7 this.rank = new Array(n).fill(1); // 노드가 한 트리의 루트인 경우 해당 트리의 높이를 저장한다.
8 }
9 /**
10 * @param u
11 * @return {number} The root node
12 */
13 find(u) {
14 if (u === this.parent[u]) return u;
15 // parent[u]를 루트로 바꿔 다음번에 find(u)가 호출됐을 때는 경로를 따라 찾아 올라갈 필요가 없어지게 한다(경로 압축; path compression).
16 return this.parent[u] = this.find(this.parent[u]);
17 }
18 /**
19 * @param {number} u Element 1
20 * @param {number} v Element 2
21 */
22 merge(u, v) {
23 let u_root = this.find(u);
24 let v_root = this.find(v);
25
26 if (u_root === v_root) return;
27
28 if (this.rank[u_root] > this.rank[v_root]) [this.rank[u_root], this.rank[v_root]] = [this.rank[v_root], this.rank[u_root]];
29 // 이제 rank[v_root]가 항상 rank[u_root] 이상이므로 u_root를 v_root의 자식으로 넣는다.
30 this.parent[u_root] = v_root;
31
32 if (this.rank[u_root] === this.rank[v_root]) this.rank[v_root]++;
33 }
34}

이렇게 최적화를 마친 DisjointSet은 찾기와 합치기 연산을 아주 많이 수행했을 때, 각 수행에 대해 상수 시간에 동작한다. 구현이 간단하고 동작 속도가 아주 빠르기 때문에 다른 알고리즘의 일부(대표적으로 Kruscal)로 사용되는 경우가 많다.

참조: 알고리즘 문제 해결 전략 2