유니온 파인드란?

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

• union 연산
  각 노드가 속한 집합을 1개로 합치는 연산
  노드 a,b가 a ∈ A, b ∈ B 일 때 union(a,b)는 A ∪ B를 말한다.

• find 연산
  특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산
  노드 a가 a ∈ A 일 때 find(a)는 A 집합의 대표 노드를 반환한다.

원리

1. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다.

   [1]	[2]	[3]	[4]	[5]	[6]
   1	2	3	4	5	6

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다.

   union(1,4)
   union(5,6)

   ➩ 리스트[4]는 1로, 리스트[6]은 5로 변경

   [1]	[2]	[3]	[4]	[5]	[6]
   1	2	3	1	5	5

   1은 대표 노드, 4는 자식 노드로, 대표 노드 1로 변경한 것이다. 그럼 이제 4와 6을 합쳐볼게요.

   union(4,6)

   4와 6을 합치기 위해선 각 노드의 대표 노드를 찾아 올라간 다음 그 대표 노드를 연결해야 한다.
   리스트[4]와 리스트[6]의 대표 노드는 1과 5입니다.
   따라서 union(4,6) 의 결과는 리스트[6] 의 대표값 5를 리스트[4]의 대표 노드 1로 변경된다.

   [1]	[2]	[3]	[4]	[5]	[6]
   1	2	3	1	1	5

3. find 연산
   자신이 속한 집합의 대표 노드를 찾는 연산
   find 연산은 단순히 대표 노드를 찾는 역할뿐만 아니라, 그래프를 정돈하고 시간 복잡도를 줄인다.

   1) 대상 노드 리스트에 index값과 value값이 동일한지 확인
   2) 동일하지 않으면 value값이 가리키는 index 위치로 이동
   3) 이동 위치의 index 값과 value값이 같을 때까지 1~2 반복, 이 부분은 재귀로 구현한다.
   4) 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경한다.

   예를 들어)
   find(4) : 4의 부모를 찾아라
   리스트[4] 값이 4인지 확인하고 동일하지 않으니 리스트[4]의 값(1)이 가리키는 index로 이동한다.
   리스트[1] 값이 1인지 확인하고, 같다면 리스트[1]의 값 1를 리턴한다.
   재귀함수를 빠져나오며 리스트[4]의 값은 1이 된다.
   즉, 리스트[4]의 대표 노드는 1이 된다.

   def findParent(num):
   	if A[num] != num:
     		A[num] = findParent(num)
     	else:
         	return A[num]
     	

문제

집합의 표현 - 백준 1717번

예제 입력1

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력1

NO
NO
YES

풀이

kind가 0이면 union, kind가 1이면 find(대표노드)가 같은지 확인

1. findParent(num) 함수
   find 함수, 대표노드를 찾는 함수이다.
   리스트[num] 과 num이 다르면 리스트[num]의 값으로 다시 findParent(리스트[num])
   리스트[num] 과 num이 같으면 리스트[num]을 return 하고, 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경한다.

   def findParent(num):
       if A[num] != num:
           A[num] = findParent(A[num])
       return A[num]

2. kind가 0이면 union(a,b)
   a와 b의 대표 노드를 찾고, 다르면 대표 노드 값 갱신

3. kind가 1이면 a 대표 노드값과 b 대표 노드값이 같은지 비교

코드

# 집합의 표현
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)

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


def findParent(num):
    if A[num] != num:
        A[num] = findParent(A[num])
    return A[num]


for i in range(m):
    kind, a, b = map(int, input().split())
    parent1 = findParent(a)
    parent2 = findParent(b)

    if kind == 0:  # a, b 합친다
        if parent1 != parent2:
            A[parent2] = parent1
    elif kind == 1:
        if parent1 == parent2:
            print("YES")
        else:
            print("NO")

정리하며

처음에 시간 초과 났다.
find 구현을 대표노드를 찾고 업데이트를 해놓지 않아서 시간이 오래 걸렸다 ㅠ
항상 부모 노드를 찾을 때마다 꼬리에 꼬리를 물어 찾아냈다.

if A[num] != num:
  	return findParent(num)

이 부분에서 return 대신 A[num]에 반영하여 부모노드를 바로 반영했다.

if A[num] != num:
  		A[num] = findParent(num)