0. 배경

  • Disjoint Set : 공통 원소가 없는 상호 배타적인 집합 (서로소 집합)
    • 예를 들어 집합 {1, 2} 집합 {3, 4} 는 서로소 관계이다. 반면 집합 {1, 2} 와 집합 {2, 3} 은 2 라는 원소가 두 집합에 공통적으로 포함되어 있어 서로소 관계가 아니다.

1. 정의

  • 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 (또는 알고리즘)
  • 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

2. 3가지 연산

  • Union-Find를 구현하기 위해 3가지 연산이 필요하다.
  • 합치기(union), 찾기(find) 이 두 연산을 지원한다고 해서 Union-Find라고 부른다.
  1. 초기화 : n 개의 원소가 각각의 집합에 포함되어 있도록 초기화한다.
  2. 합치기(union) 연산 : 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합친다.
    • 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  3. 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환한다.
    • 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

3. 배열로 표현하기

01. 개념

  • 가장 간단한 방법인 1차원 배열 하나를 이용한다.

02. 구현

  • belongsTo[i] = i번 원소가 속하는 집합의 번호
  1. 초기화 : belongsTo[i] = i 로 각자 다른 숫자로 초기화 한다.

  2. 합치기(union) 연산 : 모든 원소를 순회하면서 한쪽 집합에 속한 원소들을 다른 쪽 집합으로 옮겨 주어야한다. 이는 belongsTo[]의 모든 원소를 순회하며 집합의 번호를 다 수정해줘야 하는데 O(n) 시간이 걸린다.

    union-find를 배열로 표현

  3. 찾기(find) 연산 : 배열 각 원소가 속하는 집합의 번호를 가지고 있다. (O(1) 시간 안에 가능)
  • 찾기 연산이 빨라서 좋지만, 합치기 연산을 거의 쓰지 않는다면 모를까 일반적으로 배열 방식은 쓰기 힘들다. 그래서 찾기 연산에 시간이 좀 더 걸려도 합치기 연산을 빠르게 할 수 있는 방법이 필요하다.

4. 트리로 표현하기

union-find를 트리로 표현

01. 개념

  • 위의 배열로 표현한 것의 문제를 개선할 수 있는 방법이다.
  • 한 집합에 속하는 원소들을 하나의 트리로 묶어준다. 따라서 상호 배타적 집합 자료 구조는 트리들의 집합으로 표현된다.

  • 항상 부모 테이블을 유지한다. (배열을 이용해 트리 표현)

  • 찾기(find) 연산
    • 트리와 루트는 항상 1:1 대응이다. 그래서 루트가 같다면 두 노드가 같은 트리에 속해있음은 자명하다.
    • 주어진 원소가 포함된 트리의 루트를 찾는 것으로 찾기 연산을 구현한다.
    • 이런 찾기 연산을 구현하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 한다. 반면 부모에서 자식으로 내려갈 일은 없기 때문에 부모는 자식에 대한 포인터를 가지고 있을 필요가 없다.
      • 그림에서 모든 화살표가 자식에서 부모로 연결되는 이유이다.
      • 따라서 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.
    • 또한 루트는 부모가 없으므로, 대개 자기 자신을 가리키도록 구현한다.
  • 합치기(union) 연산
    • 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣으면 된다.

02. 과정

union-find 과정

03. 구현

  1. 초기화 : 모두 각자 다른 집합이 된다. 각 노드는 모두 루트 노드가 되며, N개의 루트 노드를 생성하고 자기 자신을 가리키는 포인터를 가지도록 설정한다.
  2. 합치기(union) 연산 : 각 트리의 루트 노드를 찾은 뒤 다르다면, 하나를 다른 한쪽의 자손으로 넣어 두 트리를 합친다. (union의 수행시간은 find가 지배하기 때문에 find와 같은 시간이 걸린다.)
  3. 찾기(find) 연산 : 각 노드에 저장된 포인터 정보를 따라가 주어진 원소가 포함된 트리의 루트 노드를 찾는다. (해당 트리의 높이에 비례하는 시간이 걸린다.)
class DisjointSet {
	constructor(n) {
		this.parent = Array.from({length: n}, (_, i) => i); // init
	}

	// u가 속한 트리의 루트의 번호를 반환
	// u가 루트 노드가 아니라면, 루트를 찾기 위해 재귀 호출
	find(u) {
		if (u === this.parent[u]) return u;
		return this.find(this.parent[u]);
	}

	// u가 속한 트리와 v가 속한 트리를 합친다.
	union(u, v) {
		u = this.find(u);
		v = this.find(v);

		// u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
		if (u === v) return;
		this.parent[u] = v;
	}
}

5. 최적화

랭크에 의한 합치기 최적화

00. 문제의 발견

  • 트리의 표현은 배열의 표현보다 개선된 표현이지만, 연산의 순서에 따라 잘못하면 트리가 한쪽으로 기울어질 수 있다는 문제가 있다.
  • 예를 들어 두 트리 a와 b를 합칠때, a의 루트를 항상 b의 루트의 자식으로 넣는다고 하자. 그러면 0과 1을, 1과 2를, 2와 3을 합치기를 반복하면 높이는 n-1인 트리, 아니 연결 리스트가 생긴다.
  • 이렇게 높이가 O(n)이 되면, union, find 연산 모두 O(n)이 된다. 애초에 배열보다 더 효율이 떨어진다. (이전에 이진 검색 트리에서도 봤던 문제)

01. 해결 1 : 랭크에 의한 합치기 (union-by-rank) 최적화

  • 두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지한다.

  • 구현

    1. rank[] 는 해당 노드가 한 트리의 루트인 경우 해당 트리의 높이를 저장한다.
    2. union 연산 시에 높이가 낮은 쪽을 높은 트리의 서브트리로 포함한다.
    3. 두 트리의 높이가 같은 경우에만 결과 트리의 높이를 1 늘려주는 방식으로 구현한다.
    // 위의 코드에서
// 생성자에 rank 배열 추가
// union 연산시 트리 높이 비교하는 부분과 높이 같은 경우 처리하는 부분 추가

constructor(n) {
	this.parent = Array.from({length: n}, (_, i) => i); // init
	this.rank = Array.from({length: n}, () => 1); // 추가된 부분!!
}

// u가 속한 트리와 v가 속한 트리를 합친다.
union(u, v) {
	u = this.find(u);
	v = this.find(v);

	// u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
  if (u === v) return;
	if (this.rank[u] > this.rank[v]) { // 추가된 부분!!
		const temp = u;
		u = v;
		v = temp;
  }

  // 이제 rank[v]가 항상 rank[u] 이상이므로 u를 v의 자식으로 넣는다.
	this.parent[u] = v;
	if (this.rank[u] === this.rank[v]) ++this.rank[v];
}
  • 개선점
    • 이 최적화를 이용하면 트리의 높이는 합쳐진 두 트리의 높이가 같을 때만 증가하므로, 높이가 h인 트리가 생기기 위해서는 높이가 h-1인 두 개의 트리가 합쳐져야 한다.
    • 트리의 높이가 h-1이기 위해 최소 x개의 노드가 필요하다면, 높이가 h가 되기 위해서는 최소 2x개의 노드가 필요하다. (높이가 h+1이기 위해 4x개의 노드 필요, 2배씩 늘어남)
    • 따라서 트리의 높이는 포함한 노드의 수의 로그에 비례하며 union, find 연산의 시간복잡도는 O(N)이 아니라 O(logN)이다.

02. 해결 2 : 경로 압축 (path compression) 최적화

경로 압축 최적화

  • 찾기 연산이 중복된 계산을 여러번 하고 있다는 데 착안한다.
  • find(u)를 통해 u가 속하는 루트를 찾아냈다고 하자. 이때 parent[u]를 찾아낸 루트로 아예 바꿔 버리면 다음번에 find(u)가 호출되었을 때는 경로를 따라 올라갈 것 없이 바로 루트를 찾을 수 있을 것이다.

  • 구현

    • find()를 재귀적으로 구현해서, find(u)를 호출하면 u에서 루트까지 올라가는 경로 상에 있는 모든 노드들에도 경로 압축 최적화가 자동으로 수행된다.
    // 재귀적으로 올라가면서 경로 압축 최적화 로직 추가

// u가 속한 트리의 루트의 번호를 반환
find(u) {
	if (u === this.parent[u]) return u;
	return this.parent[u] = this.find(this.parent[u]); // 수정된 부분!! (=과 return 동시)
}

6. 정리

  • 언어 : JavaScript

  • 최종 코드

    class DisjointSet {
	constructor(n) {
		this.parent = Array.from({length: n}, (_, i) => i); //init (편의상 0 번 정점 유지)
		this.rank = Array.from({length: n}, () => 1);
	}

	// u가 속한 트리의 루트의 번호를 반환
	find(u) {
		if (u === this.parent[u]) return u;
		return (this.parent[u] = this.find(this.parent[u]));
	}

	// u가 속한 트리와 v가 속한 트리를 합친다.
	union(u, v) {
		u = this.find(u);
		v = this.find(v);

		// u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
		if (u === v) return;
		if (this.rank[u] > this.rank[v]) {
			const temp = u;
			u = v;
			v = temp;
		}
		// 이제 rank[v]가 항상 rank[u] 이상이므로 u를 v의 자식으로 넣는다.
		this.parent[u] = v;
		if (this.rank[u] === this.rank[v]) ++this.rank[v];
	}
}
  • 두 가지 최적화를 모두 적용한 Disjoint Set의 수행시간을 분석하기란 아주 까다롭다. find 연산은 호출할 때마다 수행시간이 바뀌기 때문이다.
  • 각 수행에 걸리는 평균시간은 O(a(n))이라고 한다.
  • a(n)은 애커만 함수를 이용해 정의되는 함수로 자세한 설명은 생략하고, 중요한 것은 우리가 상상할 수 있는 모든 크기의 n에 대해 4이하의 값이라는 사실이다.
  • 따라서 현실적인 모든 입력에 대해 상수 시간에 동작한다고 봐도 좋다.
  • 사용되는 경우
    • 그래프의 연결성 확인
    • 가장 큰 집합 추적
    • 무 방향 그래프 내에서의 사이클 찾기

7. 출처