[Algorithm] 유니온 파인드(Union-Find) 개념, 코드(C++)

1. 유니온 파인드

1) 의미

- 그래프 알고리즘으로 Union(합집합) + Find(찾다)로 '합집합 찾기' 라는 의미를 가지고 있다.

- 서로소 집합(Disjoint Set) 이라고 불리기도 한다.

- 여러 노드 중 두 노드를 선택하여 같은 그래프에 속해 있는 지 확인하는 알고리즘이다. 

 

2) 연산

- 2가지 연산이 존재한다.

① Find(x) : 원소 𝑥가 속한 부분집합을 찾는다. 보통 𝑥가 속한 부분집합의 대표 원소를 되돌려준다

② Union(x, y) : 원소 𝑥가 속한 부분집합과 원소 𝑦가 속한 부 분집합의 합집합을 구한다.

* 각 부분집합은 트리로 나타낸다.

 

3) 구현(배열 이용)

- 미리 해야할 과정 

• 노드의 개수 만큼 배열을 선언한다.
• 각 노드의 루트노드를 가르키는 배열을 선언하고, 초기화 한다. (parent배열)
• 주어진 조건에 맞게 각 노드의 parent 배열의 값은 그 노드가 가르키는 노드로 바꿔준다.

 

ⓐ Find : 루트 노드를 찾는 함수이므로 루트에 도달할 때까지 계속 부모노드를 찾아 올라간다.

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

ⓑ Union : 𝑥를 (혹은 𝑦를) 포함하는 부분집합을 나타내는 트리를 다른 것의 부트리로 만들면 된다.

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	parent[y] = x;
}

- x, y가 매개변수로 들어왔을 때, x와 y의 루트노드가 같다면 같은 집합이므로 종료하고,

아니라면 y의 부모를 x로 바꿔준다.

 

 

ⓒ 시간복잡도 

- 일반적으로 유니온파인드를 사용하면, 평균적으로 트리의 높이만큼 탐색하게되므로 시간복잡도는 O(logn)이된다.

- 최악의 경우로 경사트리일때는 트리의 높이가 n이므로 시간복잡도는 O(N)이다.

따라서 시간복잡도는 O(logn)~O(N) 이다.

 

2. 유니온 파인드의 가중법칙

- union(𝑥,𝑦) 연산에서 원소 𝑥와 𝑦가 속한 부분집합에 대한 트리를 각각 𝑇𝑥, 𝑇𝑦라고 할 때,

  𝑇𝑥의 노드 개수가 더 많으면 𝑇𝑦의 루트를 𝑇𝑥의 루트의 자식이,

  그렇지 않으면 𝑇𝑥의 루트를 𝑇𝑦의 루트의 자식이 되도록 만든다.

>>> 가중 법칙에 따라 구성된 트리의 높이는, 노드 개수를 𝑛이라고 할 때, log2 𝑛 을 넘지 않는다.

 

- 증명 : (수학적 귀납법으로 증명한다)

• 𝑛 = 1인 기본 경우는 ℎ = 0 = log2 𝑛 이므로 성립한다.
• 𝑛 ≥2라고 둔다. 𝑇𝑖의 노드 개수를 𝑛𝑖 , 높이를 ℎ𝑖라고 두고, 𝑛1 ≥ 𝑛2이라고 가정한다.
• 그러면 ℎ = max ℎ1, ℎ2 + 1 이다.
• ℎ1 ≤ log2 𝑛1 ≤ log2 𝑛 이고,
• ℎ2 ≤ log2 𝑛2 ≤ log2 𝑛 2 ≤ log2 𝑛 − 1이다.
• 따라서 ℎ ≤ log2 𝑛 이 성립한다.

 

 

+ 유니온 파인드 백준문제 : 1717번: 집합의 표현 (acmicpc.net)

1717번: 집합의 표현

개념 이해하고 풀어보면 좋을 듯!