서로소 집합(Disjoint-set) - Union-Find 알고리즘

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 서로소 집합(Disjoint-set) - Union-Find 알고리즘

1) 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들

- 겹치지 않는 집합

 

2) 교집합이 없음

 

3) 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 -> 대표자

- 예를 들어, A = {1,3,5}, B = {2,4,6)이 있을 때, A 집합에서는 1, B 집합에서는 2를 식별자로 둔다. 즉, 식별자는 대표자가 된다.

 

4) 서로소 집합을 표현하는 방법

- 연결 리스트

- 트리

 

5) 서로소 집합 연산

- Make-Set(x) : 다 쪼개어진 단위 집합을 만드는 연산 (최초 1번만 수행)

- Find-Set(x) : x가 속한 집합을 찾는 연산

- Union(x,y) : x와 y가 속한 집합을 합쳐주는 연산

 

6) 서로소 집합을 표현하는 방법 - 연결리스트

- 같은 집합의 원소들은 하나의 연결리스트로 관리

- 연결리스트의 맨 앞의 원솔르 집합의 대표 원소로 지정

- 각 원소는 집합의 대표원소를 가리키는 링크를 가짐

 

7) 서로소 집합을 표현하는 방법 - 트리

- 하나의 집합을 하나의 트리로 표현

- 자식 노드가 부모 노드를 가리킴

- 루트 노드가 대표자가 된다.

 

8) 서로소 집합에 대한 연산의 효율을 높이는 방법

i) Rank를 이용한 Union

- 각 노드는 자신을 루트로 하는 서브트리의 높이를 Rank라는 이름으로 저장

- 두 집합을 합칠 때 Rank가 낮은 집합을 Rank가 높은 집합에 합침

 

ii) Path compression

- Find-Set을 하는 과정에서 만나는 모든 노드들이 직접 Root를 가리키도록 포인터 변경

 

Union-Find 관련 문제

yongku.tistory.com/entry/SW-expert-Academy-SWEA-3289%EB%B2%88-%EC%84%9C%EB%A1%9C%EC%86%8C-%EC%A7%91%ED%95%A9-%EC%9E%90%EB%B0%94Java

[SW expert Academy] SWEA 3289번 서로소 집합 자바(Java)