[자료구조 및 알고리즘] 서로소 집합 (disjoint set)

서로소 집합

 

서로소 집합은 집합 관계를 표현하는 자료구조로, 공통 원소가 없는 두 집합을 말한다. 서로소 집합 알고리즘은 union-find 연산으로 구성된다. 그래서 서로소 알고리즘을 union-find 알고리즘으로 부른다고도 한다.

 

union(합집합 연산), find(찾기)

 

union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

 

• union(x,y): x가 속한 집합과 y가 속한 집합을 합친다.
• find(x): x가 속한 집합의 대표 번호(루트 노드)를 반환한다.

1. union 연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다.

  1-1. A와 B의 루트 노드 A', B'를 찾는다

  1-2. A'를 B'의 부모 노드로 설정한다.

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

일반적으로, 구현할 때는 A'와 B' 중에서 더 번호가 작은 원소가 부모 노드가 되도록 구현한다.

=>  union 연산을 하나씩 확인하면서 서로 다른 두 원소에 대해 합집합을 수행해야할 때는 각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 하면 된다.

---

union-find 연산 과정

 

1. parent 배열 생성. parent 배열은 노드의 부모 노드를 저장한다. 부모 노드가 없다면 자기 자신을 가리킨다. 이 연산은 앞으로 있을 union, find 연산에 사용된다.

parent = [i for i in range(10)]

 

2. find

 

find 연산은 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표 원소(루트 노드)를 반환하는 연산이다. 이 연산은 대표 원소에 도달할 때까지 부모 배열을 재귀적으로 순회한다.

def find(x):
  if x == parent[x]:
    return x
  return find(parent[x])

위의 식은 최악의 경우 O(N)의 시간복잡도를 가질 수 있다. 이를 개선할 수 있는 방법이 있는데 바로 경로 압축이다. 이는 find 연산을 수행할 때마다 트리의 구조를 평평하게 만드는 방법이다. 루트 노드까지 순회 중 방문한 각 노드들이 직접 루트 노드를 가리키도록 하여 모든 노드들은 같은 대표 노드를 공유하게 된다. 평평한 트리가 만들어진 이후에는 O(1)만에 find 연산을 수행할 수 있다.

def find(x):
  if x != parent(x):
    parent[x] = find(parent[x])
   return find(parent[x])

3. union

 

union 과정은 다음과 같다.

1. find 연산을 통해 두 요소의 루트 노드를 찾는다.

2. 두 루트 노드 중 하나를 다른 트리의 루트 노드 아래에 배치하여 두 트리를 합친다.

def union(a,b):
  a = find(a)
  b = find(b)
  
  parent[b]=a

 

더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 하려면 아래와 같이 하면 된다.

def union(a,b):
  a = find(a)
  b = find(b)
  if a < b:
    lst[b] = a
  else:
    lst[a] = b

 

완성하면 다음과 같다. 참고로 다음 코드는 백준 1717번 집합의 표현 문제의 답이다. union-find 알고리즘을 그대로 사용하면 해결된다.

n,m = map(int, input().split())
set = [i for i in range(n+1)]

def find(a, parent):
  if a != parent[a]:
    parent[a] = find(parent[a], parent)
  return parent[a]

def union(a,b,parent):
  a = find(a, parent)
  b = find(b, parent)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

for _ in range(m):
  o,a,b = map(int, input().split())
  if o == 0:
    union(a,b,set)
  elif o == 1:
    if find(a,set) == find(b,set):
      print("YES")
    else: print("NO")

 

참고

https://zz132456zz.tistory.com/11

[알고리즘] 서로소 집합 (Disjoint Sets Algorithm)

https://laboputer.github.io/ps/2017/10/07/disjointset/

[자료구조 2] 서로소 집합(Disjoint Set) 이해하기