[Algorithm] Disjoint Set & Union-Find

6720·2023년 7월 26일

algorithm

이거 모르겠어요

목록 보기

28/38

Disjoint Set

서로소 집합

서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말함.
보통 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는 데 사용됨.

Union-Find

Disjoint Set을 표현할 때 사용하는 알고리즘
주로 크루스칼 알고리즘을 구현할 때나 그래프 사이클을 탐지할 때 사용함.

연산

MakeSet

주어진 요소만 포함하는 집합을 생성
make-set(x): x를 유일한 원소로 하는 새로운 집합 생성

Union

두 개의 집합을 하나의 집합으로 합치는 연산
union(x, y): x와 y가 속한 두 집합을 합치는 연산

Find

어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표 원소를 반환하는 연산
find(x): x가 속한 집합의 대표 반환 → x가 어떤 집합에 속해 있는지 찾는 연산

+) Union-Find 알고리즘을 트리 구조로 구현하는 이유

집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 트리 구조를 이용하여 구현하는 됨.

배열 구조: arr[i] = i번 원소가 속하는 집합의 번호. 즉, 루트 노드의 번호
트리 구조: 같은 집합 = 하나의 트리. 즉, 집합 번호 = 루트 노드

	배열 구조	트리 구조
make-set(x)	각자 다른 집합 번호로 초기화 EX) arr[i] = i	N개의 루트 노드 생성 및 자기 자신으로 초기화
union(x, y)	배열의 모든 원소 순회, y의 집합 번호를 x의 집합 번호로 변경, O(N)	y를 x의 자손으로 넣어 두 트리를 합함. O(N)보다 작아서 find 연산이 전체 수행 시간을 지배함.
find(x)	한 번 만에 x가 속한 집합 번호를 찾음. O(1)	루트 노드를 확인하여 같은 집합인지 확인 트리의 높이와 시간 복잡도 동일 (최악 O(N-1))

코드

// MakeSet
int[] parent = new int[N + 1];
for (int i = 0; i < parent.length; i++) {
		parent[i] = i;
}

// Find
private int find(int x) {
		if (parent[x] == x) return x;
		return find(parent[x]);
}

// Union
private boolean union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return false;

		if (x <= y) parent[y] = x;
		else parent[x] = y;
		return true;
}

개선

Union 연산과 Find 연산의 성능이 트리의 높이에 크게 의존함.
트리 구조가 완전 비대칭인 경우 (연결 리스트 형태) 트리의 높이가 최대가 됨.
트리의 개수가 N이라고 하면 트리의 높이는 N-1이 되기 때문에 Union 연산과 Find 연산의 시간 복잡도가 모두 O(N)이 됨.
성능을 높이기 위해선 높이를 최소화해야 함.
아래의 두 방법을 사용하면 시간 복잡도를 O(logN)으로 줄일 수 있음.

경로 압축

Path Compression (Find 연산 최적화)

위의 트리처럼 5번이 3번과 같은 집합에 있음을 확인하기 위해선 1번 노드까지 거슬러 올라가야 하므로 비효율적임.

따라서 한 노드에 대해 Find 연산을 실행할 때마다 그 노드의 부모 노드를 항상 루트 노드로 만들어준다면, 더 효율적으로 루트 노드를 찾을 수 있음.

// Find - Path Compression
private int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
}

Union-By-Rank

Union-By-Height (Union 연산 최적화)

Union 연산 시 항상 높이가 낮은 트리를 높은 트리에 붙임으로써 시간 복잡도를 줄일 수 있음.
→ 높이가 높은 트리가 낮은 트리에 붙을 경우, 합쳐진 트리의 높이가 더 많이 증가하기 때문
높이가 낮은 트리를 높은 트리에 붙인다는 말은 높이가 더 높은 쪽을 루트로 삼는다는 의미

// MakeSet
int[] parent = new int[N + 1];
int[] rank = new int[N + 1]; // 높이
for (int i = 0; i < parent.length; i++) {
		parent[i] = i;
		rank[i] = 0;
}

// Union
private void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return;

		if (rank[x] < rank[y]) parent[x] = y;
		else {
				parent[y] = x;
				if (rank[x] == rank[y]) rank[x]++; // 높이가 같을 경우 합친 후 x의 높이 +1
		}
}

+) Union-By-Size: 트리의 노드 수를 이용한 최적화
노드 수가 작은 트리를 큰 트리에 붙임.

// MakeSet
int[] parent = new int[N + 1];
int[] rank = new int[N + 1]; // 높이
for (int i = 0; i < parent.length; i++) {
		parent[i] = i;
		rank[i] = 0;
}

// Union
private void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x == y) return;

		if (rank[x] < rank[y]) {
				parent[x] = y;
				rank[y] += rank[x];
		} else {
				parent[y] = x;
				rank[x] += y;
		}
}