[Disjoint Set] Union Find 알고리즘
- Algorithm
- 2021년 4월 12일
1. Disjoint Set
번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합이다.
2. Union-Find
- Union : 두개의 집합을 하나의 집합으로 합치는 것.
- Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것.
집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단할때 각 집합의 대표값(root)을 이용해서 집합이 같은지를 비교.
3. 구현 방법
1) 연결리스트
typedef struct node{
int data;
struct node* parent;
struct node* next;
}node;
void MakeSet(node* p,int x){
p->data = x;
p->parent = p;//처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
p->next=null;
}
void Find(node* p,int x){
if(p->parent->data == x) return x; //root값이 자기 자신이라면 집합의 대표값
else return Find(p->parent,x); //재귀적으로 집합 대표값 찾기
}
void Union(node* p1,node* p2,int x,int y){
x = Find(p1,x);
y = Find(p2,y);
p1->next = p2;
p2->parent = p1;
}
2) Disjoint Set Forest ( Tree )
int root[n];
void MakeSet(int x){
root[x] = x; //처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
}
void Find(int x){
if(root[x] == x) return x; //root값이 자기 자신이라면 집합의 대표값
else return Find(root[x]); //재귀적으로 집합 대표값 찾기
}
void Union(int x,int y){
x = Find(x);
y = Find(y);
root[y] = x;
}
4. 시간 복잡도
연결리스트로 구현시 O(nlgn) 의 시간을 갖으며 Tree로 구현해도 불균형한 트리 (예 : skewd tree)와 같게 되면 연결리스트와 다를 것이 없어진다.
5. 문제점
find시에 재귀적으로 찾기 때문에 만약에 set의 tree구조가 선형적인 형태라고 한다면 최악의 경우로 O(n)만큼의 시간이 소요 되게 된다.
➡ path compression (경로 압축) 기법 사용
또한, union시에 깊이가 작은 트리에 깊이가 깊은 트리를 붙이게 되면 깊이가 더 증가하여 시간에 악영향을 준다.
➡ union by rank 기법 사용
6. path compression (경로 압축)
find 연산 수행시마다 트리의 구조를 평평하게 만드는 방법으로 각 root값을 재귀적으로 가리키는 것이 아닌 해당 집합의 속하는 원소는 모두 동일한 root를 가리키게 만드는 방법이다.
void Find(int x){
/*find수행마다 해당 parent값을 root로 초기화*/
if(root[x] != x) root[x] = Find(root[x]);
else return root[x];
}
7. union by rank
항상 깊이가 깊은 트리에 작은 트리를 붙여 깊이를 유지하는 방법으로 깊이가 서로 같은 트리라면, 깊이를 1증가 시키게 된다.
int root[n];
int rank[n];
void MakeSet(int x){
root[x] = x; //처음은 다 원소가 하나씩있는 집합이므로 자기 자신이 root
rank[x] = 0; //깊이도 0으로 초기화
}
void Union(int x,int y){
x = Find(x); //입력받은 x값의 root값을 저장
y = Find(y); //입력받은 y값의 root값을 저장
if(x==y) return; //root가 같다면 같은 집합
if(rank[x] < rank[y]) root[x] = y; //x의 root를 y로 변경
else if(rank[x] > rank[y]) root[y]= x; //y의 root를 x로 변경
else{
root[y] = x;
rank[x]++; //깊이가 같다면 x에 y를 붙였으므로 x깊이 증가
}
8. 두 기법을 적용 후 시간 복잡도
O(lgn)
9. 활용
Disjoint Set 자료구조는 집합의 분할을 모델링 하기 때문에 무방향 그래프(undirected graph) 의 연결된 요소들을 추적 할 수 있어, 사이클이 발생하는지 또는 같은 요소에 속하는지 확인 할 수 있고 대표적으로 MST를 찾는 Kruskal 알고리즘에 이용된다.