[알고리즘] 유니온 파인드

두 노드가 같은 집합에 속해 있는지를 확인하는, find연산으로 구성된 알고리즘

핵심 이론

• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어있는 알고리즘이다.

• 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 한다.

• 서로소 집합을 구하는 알고리즘이다. 서로소 집합은 공통 원소가 없는 집합들을 뜻한다.

유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다!

union 연산

• 두 집합을 하나로 합치는 연산.

• '두 집합을 합친다' = '루트 노드를 같게 한다'

• P : 하지만 트리의 깊이가 깊어지면 연산 비용이 커진다.

• S : 랭크로 해결.

랭크란? 현재 노드를 기준으로 했을 때 가장 깊은 노드까지의 경로 길이를 말한다.

• 루트 노드의 랭크를 비교하여, 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼고, 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꾼다.

find 연산

• 특정 노드의 루트 노드가 무엇인지 탐색하는 방법.

• 특정 노드가 같은 집합에 있는지 확인할 때 사용한다.

  	- A, B의 루트 노드가 서로 같다면 같은 집합에 속한 것!

• 서로 다른 두 노드의 루트 노드를 탐색할 때는 재귀 함수로 구현한다. 루트 노드를 현재 노드와 부모 노드가 같을 때까지 재귀함수를 실행해 최종값을 반환하면 됨.

• P : 최악의 경우 시간 복잡도가 O(N)

• S : 경로 압축

동작 방법

1. 부모 테이블 초기화 (노드의 배열을 인덱스 자기 자신으로 초기화)

parent = [i for i in range(n+1)]

2. union 연산 확인
   2-1. 모든 주어진 union연산에 대해 서로 연결된 두 노드를 확인.
   2-2. A의 루트 노드 A'와 B의 루트 노드 B'를 찾기(find)

   def find(x):
   # 만약 x의 부모가 자기자신이 아니라면 재귀를 통해 루트 노드를 찾는다.
   if parent[x] != x:
       return find(parent[x])
   # 자기자신이라면 본인이 루트노드인 경우이므로 그대로 출력한다.
   return parent[x]

   • 경로 압축 (parent[x]를 return) 하여 루트 노드에 더 빠르게 접근하게 함.

   2-3. A'의 rank가 B'보다 낮다면, A'를 B'의 부모 노드로 설정.

   def union(a,b):
   # a와 b의 루트노드 찾기
   a = find(a)
   b = find(b)
   # 둘 중 원소 값이 작은 원소를 루트노드로 정하여 저장한다.
   if a<b:
       parent[b]=a
   else:
       parent[a]=b

3. 모든 union연산을 처리할 때까지 2번 반복.

---

참고
https://todays-mine.tistory.com/52
https://velog.io/@woo0_hooo/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-union-find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98