유니온 파인드(Union-Find)

오늘은 그래프 알고리즘 중 하나인 유니온 파인드(Union-Find)에 대해 알아보겠습니다!

 

유니온 파인드는 합집합 찾기, 서로소 집합(Disjoint Set) 알고리즘 등 다양한 이름으로 불리는데욥

그래프에서 같은 그래프에 속하는지 확인(각 노드의 연결 여부 확인)하거나, 같은 집합인지 확인하는 

즉. 같은 소속인지 확인하는 알고리즘입니다!

 

특히 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 크루스칼 알고리즘(Kruskal's Algorithm)에 기반이 되는 알고리즘 입니다

간선을 연결할 때 사이클이 생성되지 않도록 유니온 파인드 알고리즘을 활용하는데욥

(두 간선 연결할때, 부모노드동일할시 = 같은집할일때 -> 사이클O / 부모노드 동일하지 않을시 = 다른집합일때 -> 사이클 X)

구체적인 내용은 나중에 다뤄보겠습니다

 

# 동작과정 

유니온 파인드는 두 집합이 같은 소속인지 확인하는 알고리즘이라고 했는데욥

소속을 확인하려면 어떻게 해야 할까요?

찾으려는 두 집합 각각의 대표노드(부모노드)를 찾아 비교하면 되는데요

대표노드가 동일하면, 같은 집합 다르면, 다른 집합으로 판단할 수 있습니다

 

유니온 파인드는 2가지 연산으로 구분됩니다!

1) Union

2) Find

 

특히 대표노드를 표시하는 리스트를 생성하여 각 노드의 대표노드를 표시하는데요

인덱스(Index)-> 각 노드 번호 / 값(Value) -> 대표노드

이를 기반으로 유니온 파인드가 동작됩니다

 

1) Union

-> 각 노드가 속한 집합을 합침

각 노드의 대표노드를 업데이트하여 대표노드를 동일하게 바뀌주며 동일한 집합임을 표시합니다 

각 노드의 대표노드는 합쳐지는 노드 값 중 작은 값으로 주로 설정됩니다

 

2) Find

-> 노드의 대표 노드(부모노드 parent node) 찾기

 

2가지 경우로 구분되는데요 

해당 노드의 값(대표노드)과 각 노드의 인덱스(노드 번호)가 같음

->  대표노드값 반환

해당 노드의 값(대표노드)과 각 노드의 인덱스(노드 번호)가 다름

-> 노드의 값이 가리키는 노드의 인덱스 위치로 (동일해질때까지) 이동 (재귀적으로 반복)

 

 

구체적인 연산 과정에 대해 자세히 알아보겠습니다

1,2,3,4,5 노드에서 union 연산과 find 연산이 어떻게 수행되는지 알아보겠습니다

 

 

특히 Find 연산에는 경로 압축의 효과가 있는데요

모든 노드를 대표 노드 (parent node)에 직접적으로 연결하는 방식으로 그래프 구조를 변경하여 연산 속도가 더욱 빨라집니다 

트리의 높이가 줄어들며, 이후 연산이 더 빠르게 수행됩니다!

 

극단적인 예시로 위의 그래프를 find 연산시, 아래와 같이 직접적으로 대표노드와 연결된 구조로 변형되어 같은 집합인지 여부 확인시 더 빠른 속도로 연산을 수행할 수 있게 됩니다! (시간복잡도 O(1)로 변경)

 

최종적으로 union find 연산을 통해 집합의 대표노드를 반환하게 되고

대표노드가 동일한지 비교하며 두 집합이 같은 소속인지 여부를 확인할 수 있습니다

 

# Python 코드

union연산과 find연산을 동작과정을 기반으로 구현해 보았습니다!

parent = [i for i in range(n+1)] #각 노드의 부모노드/ 인덱스: 노드번호 / 값: 부모노드

def union(a,b): # 노드 합치기

    a = find(a)

    b = find(b)

    if a != b:

        parent[b] = a

def find(a): # 그래프의 부모노드 찾기

    if a == parent[a]:

        return a

    else:

        parent[a] = find(parent[a])

        return parent[a]

 

# 관련문제

백준 1717번 - 집합의 표현

https://www.acmicpc.net/problem/1717

 

백준 1976번 - 여행 가자

https://www.acmicpc.net/problem/1976

 

백준 1043번 - 거짓말

https://www.acmicpc.net/problem/1043

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))