DSU(Disjoint Set Union)(= 유니온 파인드 (Union-Find))

DSU

Disjoint Set (서로소 집합)이란 서로 공통된 원소가 없는 집합을 말한다.

 

= 유니온 파인드 (합집합 찾기)

공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구

2가지 union, find 연산을 지원한다.

 

1. union은 2개의 set을 하나의 set으로 합쳐주는 것

2. find는 어떤 element가 주어질 때, 이 element가 속해져 있는 대표 원소를 반환

 

여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

Union : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침 (root를 찾아서, 높이가 작은 쪽을 큰 쪽으로 합침)

→ 유니온 바이 랭크 (트리의 depth(height)르 기준으로 하여 트리를 합치며 트리의 높이가 커지는 것을 방지하기 위한 최적화 방법), 두 트리의 dpeth가 같을 경우에만 +1 증가하게 됨.

 

Find : 각 element에 저장된 포인터를 따라서 대표 원소를 반환해준다.

→ 경로 압축 (find 연산을 수행할 때마다 트리의 구조를 평평하게 만드는 방법 = 모든 대표 원소와 이어줌)

경로를 찾아가는 과정에서 원소에서 부모를 향해가며 원소와 루트 사이의 모든 원소를 방문한다.

이때 모든 원소들의 부모를 루트로 갱신해주며 경로에 존재하는 모든 원소의 부모가 루트로 이어지게 만드는 것

 

 

 

+ 이 방식의 unionParent 방식은 트리의 높이때문에 최악의 경우 O(n)이다.

이를 개선하기위해 Union-by-rank 최적화를 필요로한다.