Disjoint-Set & Union-Find

Disjoint-Set, 상호 배타적 집합

서로 중복되지 않는 부분 집합들을 의미

(교집합 존재 X)

 

Union-Find

Disjoint-Set을 표현할 때 사용하는 알고리즘.

ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 

      서로 같은 그래프에 속하는지 판단하는 그래프 알고리즘.

      이름 그대로 union 연산과 find 연산이 존재

        ▶ union(a, b) : a와 b가 포함되어 있는 집합을 합치는 연산

        ▶ find(x) : x가 어떤 집합에 포함되어 있는지 찾는 연산

 

시뮬레이션

▶ 모든 노드(정점)은 자기 자신을 가리키는 상태.

 

▶ 정점 [1] - [2] 연결 / 정점 [3] - [4] 연결 → union(1, 2) / union(3, 4)

일반적으로 두 노드 중 낮은 번호 정점으로 부모노드로 해줍니다. 

이렇게 부모를 '합치는' 과정을 『합칩union』 이라고 합니다.

(※ 어떤 기준으로 루투 부모 노드를 설정할지는 개발자 마음)

 

 

▶ 여기서, 정점 [2] - [3] 연결 → union(2, 3)

정점 [2]와 [3]을 연결하였지만, 최적화로 테이블에서 P(3) = 1 입니다.

기존에 정점 [3]의 부모 노드는 자기자신 P(3) = 3

정점[2]의 부모 노드는 P(2) = 1 로,

두 부모노드 중 낮은 번호를 가진 정점으로 합쳐줍니다.

　

Q. 정점[4]과 [2]과 같은 그래프인지 테이블에서 어떻게 판단할까? → find(4), find(2)

     (단순히 부모노드 P[4], P[2]를 비교하는 것만으로는 판단할 수 없습니다.)

find(x)를 재귀적으로 사용해서 같은지 확인!

▷ 좌항 find(4) = find(find(3)) = find(find(find(1))) = 1

▷ 우항 find(2) = find(find(1)) =  1

어떤 정점의 Root Parent Node를 찾는것 입니다.

 

Q. 왜 부모노드를 낮은 번호의 Root Parent Node가 되도록 재귀적으로 해주는 것인가요?

아래 상태에서 정점 [4], [5]를 연결(union) 해봅니다.

좌측 이미지처럼 [4], [5]가 바로 연결된다면 편향적인 그래프가 되어, 다음 연산시 비효율적이지만,

실제, find 연산 과정에서 정점[5], 정점[4], 정점[3]도 각각 Root Parent Node 찾아놓기에,

우측의 균형적인 그래프가 도출 됩니다.

 

Q. 정점 [2]와 [4] 연결해서 사이클 유무 확인하기

연결(union)시, find(4) = find(2) = 1로 (Root)부모 노드로 확인할 수 있습니다.

※ C언어에서는 공용체(union) 키워드가 존재해서 'merge'로 함수명을 짓기도 합니다.

ex) 최소신장 트리(Minimum Spanning Tree)를 구하는 

      크루스칼(Kruskal's Algorithm)에서 사이클 유무 확인

      ※ 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal)

 

※ 시간 복잡도는 평균적으로 O(α(N))으로 

    α는 애커만 함수로 링크참고

    그래프가 편향적으로 구성되었을 경우, 최악의 시간 복잡도 O(MN).

 

 

관련 문제

★ [BOJ] 10775 공항

- [BOJ] 1717 집합의 표현

- [BOJ] 1976 여행 가자

- [Jungol] 1863 종교 

- [BOJ] 2463 비용

- [SWEA] 1849 영준이의 무게측정