Disjoint Set
DisJoint Set이란?
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
- 즉, 공통 원소가 없는 "상호 배타적"인 부분집합들로 나눠진 원소들에 대한 자료구조
- Disjoint Set=서로소 집합 자료구조
Union-Find
Union-Find란?
Disjoint Set을 표현할 때 사용하는 알고리즘
-집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리 구조를 이용하여 구현
-아래의 세가지 연산을 이용하여 Disjoint Set을 표현
Union-Find의 연산
- make-set(x)
- 초기화
- x를 유일한 원소로 하는 새로운 집합을 만든다.
- union(x,y)
- x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산
-find(x)
- x가 속한 집합의 루트 노드 값을 반환한다. 즉,x가 어떤 집합에 속해 있는지 찾는 연산
※ 트리로 구현했을 때
- 같은 집합=하나의 트리, 즉 집합 번호=루트 노드
- 시간복잡도
- union(x,y) : O(n)보다 작으므로 find연산이 전체 수행 시간을 지배
- find(x) : 트리의 높이와 시간 복잡도가 동일 ( 최악 : O(N) )
구현
parent[i]를 i 노드의 부모 노드라고 정의하고 초기화 해준다.
parent[i] = i 인경우, 루트 노드임을 의미한다.
//초기화
int parent[MAX_SIZE];
for (int i=0; i<MAX_SIZE; i++)
parent[i] = i;
//fin함수 : 부모노드 찾기
int find(int x){
if (x==parent[x]){
return x;
}
else {
return find(parent[x]);
}
}
//union함수 : x의 집합과 y의 집합 합치기
void union(int x,int y){
x = find(x);
y = find(y);
if (x!=y)
parent[y] = x;
}
개선해야 될 점
- find함수에서 재귀적으로 루트를 찾아 반환해주면 그림과 같이 깊이가 깊어진 경우(최악의 경우) O(N)의 시간복잡도가 걸린다. 그래서 아래와 같이 개선해 준다.
int find(int x){
if (x==parent[x]){
return x;
}
else{
int y = find(parent[x]);
parent[x] = y;
return y;
}
}
- union 함수에서 높이가 더 높은 트리가 낮은 트리 밑으로 들어가게 되면 트리가 점점 깊어질 위험이 있다.
따라서 트리의 높이가 낮은 트리가 높은 트리 밑으로 들어가야 하는데 이를 위해서 트리의 높이를 기록해둬야 한다.
-> 추가적인 배열이 필요
결론 ) parent배열과 트리의 높이를 기록해주는 배열이 필요하므로 메모리를 두배로 사용하기 때문에
weight Union find 방법이 고안되었다.
weighted Union Find
parent 배열이 음수일 경우, 부모노드가 되어 음수의 절대값은 size(자기 자신+자식노드)가 되고, 양수일 경우에는 부모노드를 가르키게 된다.
예를 들어 parent[2]=-3인 경우 2번 노드 밑에 두 개의 자식 노드가 있어 총 3개의 노드가 존재한다는 의미이고,
parent[3]=5일 경우에는 3번 노드의 부모가 5번 노드라는 의미이다.
int parent[MAX_SIZE];
for (int i=0; i<MAX_SIZE; i++)
parent[i] = -1;
int find(int x){
if (parent[x] < 0){
return x;
}
else{
int y = find(parent[x]);
parent[x] = y;
return y;
}
}
void union(int x, int y){
x = find(x);
y = find(y);
if (x == y)
return;
// parent[x], parent[y] 값은 음수이므로 값이 작은 경우가 더 높이가 큰 노드이다.
if (parent[x] < parent[y]){
parent[x] += parent[y];
parent[y] = x;
}
else {
parent[y] += parent[x];
parent[x] = y;
}
}
관련 문제
백준 1717 집합의 표현 : www.acmicpc.net/problem/1717
참고
gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] Hash / Hash Table (0) | 2021.06.30 |
---|---|
[자료구조] 탐색(search) (0) | 2021.03.02 |
[자료구조] DFS와 BFS (0) | 2021.02.24 |
[자료구조] 그래프 (0) | 2021.02.24 |
[자료구조] 동적 계획 (DP : Dynamic Programming) (0) | 2021.02.12 |