알고리즘/이론
[알고리즘] - UnionFind
파커초
2024. 2. 5. 20:16
개요
Union-Find 는 그래프 G가 주어졌을때 상호 배타적 집합(Disjoint-Set)을 표현할때 사용되는 그래프 알고리즘입니다. 임의의 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용됩니다.
연산
- Union (합치기): 두 원소가 속한 집합을 하나로 합침
- Find (찾기): 해당 원소가 속한 집합을 반환
Find
본인이 속한 집합을 찾기 위한 연산으로 기본 방법과 경로 최적화 방법이 존재합니다.
기본 방법: 최악의 경우 시간복잡도 O(N)
int find_parent(int x) {
if(x == parent[x]) return x;
else return find_parent(parent[x]);
}경로 최적화: 시간복잡도 O(1)
int find_parent(int x) {
if(x == parent[x]) return x;
// 검색과 동시에 초기화
else return parent[x] = find_parent(parent[x]);
}Union
기본 방법: 기준을 정하고 기준대로 노드의 부모를 합칩니다. => 집합을 트리로 구성했을때 한쪽으로 치우칠 수 있습니다.
// 작은 수를 기준으로 부모 노드를 설정할때
void union_parent(int a, int b) {
int a = find_parent(a);
int b = find_parent(b);
if(b > a) {
parent[b] = a;
}
else{
parent[a] = b;
}
}최적화 방법: rank 에 트리의 높이를 저장함, 항상 높이가 더 낮은 트리를 밑에 넣음 => 집합을 트리로 구성했을때 어느정도의 balance 를 보장할 수 있습니다.
void union_parent(int a,int b) {
int a = find_parent(a);
int b = find_parent(b);
if(a == b) return;
if(rank[a] < rank[b]) {
parent[a] = b
}else if(rank[b] > rank[a]){
parent[b] = a;
}else{
parent[b] = a;
++rank[a];
}
}