유니온 파인드

유니온 파인드(Union-Find, 병합-찾기 자료구조)는 상호 배타적 집합(disjoint-set)들을 효율적으로 표현하고 조작하기 위한 자료구조이다.

개요

유니온 파인드는 원소들이 어떤 집합에 속해 있는지를 빠르게 판별하고, 두 집합을 병합하는 연산을 수행하는 데 최적화된 자료구조이다. 일반적으로 상호 배타적 집합 자료구조(disjoint-set data structure)로 불리며, 대표적으로 Kruskal의 최소 신장 트리 알고리즘 등에서 사용된다. 이 자료구조는 트리를 기반으로 구현되며, 경로 압축(path compression)과 랭크(rank) 또는 크기(size)를 활용한 병합 최적화를 통해 매우 효율적인 연산 속도를 제공한다.

연산

유니온 파인드는 두 가지 주요 연산을 제공한다. 이 연산에서 이름이 유래되었다.

• Find(x): 원소 x가 속한 집합의 대표 원소(루트)를 반환한다.
• Union(x, y): 원소 x와 y가 속한 두 집합을 하나로 병합한다.

이 두 연산을 경로 압축과 랭크 기반 병합 전략을 함께 사용할 경우, 아커만 함수의 역함수 수준의 시간복잡도를 갖게 된다.

구현

유니온 파인드는 일반적으로 트리 구조와 배열을 활용하여 구현되며, 다음과 같은 형태로 구성된다:

• 각 원소는 부모 노드를 가리키는 배열 parent[]를 가진다.
• 초기에는 모든 원소가 자기 자신을 루트로 가지는 독립된 집합이다.
• Find 연산 시 경로 압축을 통해 트리의 높이를 줄이고,
• Union 연산 시 랭크 또는 크기에 따라 루트를 결정함으로써 전체 트리의 균형을 유지한다.

응용

유니온 파인드는 다양한 알고리즘 및 문제에서 활용된다.

• 최소 신장 트리(MST) 알고리즘: Kruskal 알고리즘
• 동적 연결성 문제(dynamic connectivity)
• 네트워크 연결 상태 판별
• 사이클 검출
• 군집화 알고리즘에서 집합 관리

같이 보기

• 그래프 이론
• 최소 신장 트리
• Kruskal 알고리즘
• 경로 압축
• 자료구조

참고 문헌

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2), 215-225.