서로소 집합(Disjoint Set, Union-Find)

서로소 집합

교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조

 

2가지 연산으로 이루어져 있습니다

• Union 연산
  - 어떤 두 원소 a, b 에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산
  - a ∈ A, b ∈ B 에 대해서, union(a, b)는 A∪B 이다.
• Find 연산
  - 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환
  - a ∈ A 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환

서로소 집합 표현

배열(Array)

초기화

자기 자신의 부모를 자기 자신으로 초기화

i	1	2	3	4	5
U[i]	1	2	3	4	5

Union 연산

시간복잡도 : O(N)

union(1, 3) union(4, 5)

i	1	2	3	4	5
U[i]	1	2	1	4	4

union(5, 3)

i	1	2	3	4	5
U[i]	1	2	1	1	4

Find 연산

시간복잡도 : O(1)

find(3) = 1 find(5) = 4

i	1	2	3	4	5
U[i]	1	2	1	4	4

 

 

트리(Tree)

초기화

Union 연산

시간복잡도 : O(H), H는 트리의 높이

union(1, 3) union(4, 5) 

union(5, 3)

 

Find 연산

시간복잡도 : O(H), H는 트리의 높이

find(3) = 1 find(5) = 4

 

코드 Level

초기화

parant 배열에 i 원소에 대한 부모 노드 번호를 저장, 루트 노드인 경우 자기 자신의 번호를 저장

funtion initialize()
   for i : 1 ~ N
      parent[i] = i

 

Union 연산

하나의 루트 노드를 다른 하나의 루트 노드의 자식 노드로 넣어 두 트리를 합침

funtion Union(a, b)
   aRoot = find(a)
   bRoot = find(b)
   parent[aRoot] = bRoot

 

Find 연산

주어진 원소의 루트 노드 번호를 반환함

function find(a)
   if(parent[a] ==a)
      return a
   else
      return find(parent[a])

function find(a)
   if(parent[a] ==a)
      return a
   else
      return parent[a] = find(parent[a])

 

find(2) 예시 그림

 

유니온 파인드를 활용한 알고리즘 문제와 코드

 

steady-life.tistory.com/129

백준 1717_집합의 표현(JAVA)