Union,Find #DisjointSet #1union-by-rank #2path-compression

Disjoint Set은 매우 신박하다.

FindParent하는 과정에서 Parent를 업데이트 해줌으로써 전체적인 Operation의 Time Complexity가 O(amortized(1)) 이기 때문에, 아무때나 부수적으로 쓰일 수 있다.

따라서 모듈화하여 외워두면 좋다. ㅎㅎ

Union-Find (Disjoint Set) 코드

int Parent[MAX]; //Root로 접근하기 위해서는 반드시 FindParent(i)함수로 접근하여야 한다.

void InitDisjointSet(int n){

for(int i=0; i<n; i++){

Parent[i] = i; //각 node들이 모두 각각의 set이 된다. //Root의 조건: Parent가 자기자신

}

return;

}

int FindParent(int i){

if(Parent[i] == i) return i; //Root의 조건

Parent[i] = FindParent(Parent[i]); //찾으면서 업데이트해주는

return Parent[i];

}

void Union(int i, int j){

Parent[FindParent(i)] = FindParent(j); //j가 속한 set에 i가 속한 set이 연결되는 과정이다.

return;

}

#1. 회의

문제번호: 2610

정답비율: 28.141%

분류: 플루이드 와샬 알고리즘

비고: Disjoint Set

1. 연결되어 있는 노드끼리 Set 형성

2. 각 노드에 플루이드-와샬 적용

3. for loop 1회로 각 set 추출

4. head 결정

Q. Rank 굳이 구현해야하나?? 

이 자료구조를 optimize할 수 있는 테크닉 2개가 1. union-by-rank를 통하여 union과 find의 worst time 시간복잡도를 O(lgn)으로 줄일 수 있다. 2. path-compression을 통하여 O(a(n)) -거의 상수타임-으로 줄일 수 있다. 이 두개인데,

여기서 path-compression이 너무 강력하기 때문에 union-by-rank가 필요 없는 것 같아서요. 괜히 약간의 오버헤드만 생기게 되지 않나요?

A. Union-by-Rank가 아직도 유용한 경우

Union(1,2); Union(3,4); Union(1,3); //트리 깊이 2

Union(5,6); Union(7,8); Union(5,7); //트리 깊이 2

Union(1,5); //트리 깊이 4

이런 식으로 트리가 자라날 수 있다. 이런 경우에 대비하기 위하여 Union by Rank가 필요하다.