티스토리 뷰
목차
복잡하게 얽힌 현대 사회의 네트워크 속에서 "A와 B가 서로 소통할 수 있는가?"라는 질문은 매우 중요합니다. 수천 개의 서버가 연결된 인프라망이나 소셜 네트워크의 사용자 관계에서, 특정 두 지점이 동일한 그룹에 속해 있는지를 판별하는 작업은 효율적인 시스템 설계의 기초입니다. 이를 위해 탄생한 자료구조가 바로 서로소 집합(Disjoint Set), 일명 유니온 파인드(Union-Find)입니다. 단순한 배열로 시작하지만 '경로 압축'이라는 천재적인 최적화가 더해져 상수 시간의 속도를 내는 이 알고리즘을 2,500자 이상의 상세한 설명으로 정리하겠습니다.
1. 서로소 집합(Disjoint Set)의 정의와 논리 구조
서로소 집합이란 공통 원소가 없는 집합들을 의미합니다. 유니온 파인드는 이러한 집합들을 효율적으로 관리하기 위해 두 가지 연산을 수행합니다. 첫째, Find는 특정 원소가 속한 집합의 대표자(Root)를 찾는 연산입니다. 둘째, Union은 서로 다른 두 집합을 하나의 집합으로 합치는 연산입니다. 각 노드는 자신의 부모 노드 번호를 저장하는 배열을 통해 트리 구조로 연결되며, 루트 노드는 자기 자신을 부모로 가리킴으로써 집합의 주인임을 선포합니다.
1-1. 관계의 확인: 같은 팀인가?
두 원소가 같은 집합에 있는지 확인하는 방법은 매우 직관적입니다. 두 원소에 대해 각각 Find를 수행하여 나온 루트 노드가 일치한다면 그들은 한 팀이고, 다르다면 서로 남남입니다. 이 단순한 논리가 거대한 그래프의 연결성을 파악하는 근간이 됩니다.
2. 성능의 비결: 경로 압축(Path Compression)
유니온 파인드가 단순히 부모만 찾아 올라간다면, 트리가 한 줄로 길게 늘어지는 최악의 경우 Find 연산에 $O(N)$이 걸릴 수 있습니다. 이를 방지하는 마법이 경로 압축입니다. Find를 수행하며 루트를 찾는 과정에서, 거쳐가는 모든 노드의 부모를 루트 노드로 직접 갱신해 버리는 것입니다. 이 과정을 한 번 거치면 트리의 높이가 1로 압축되어, 다음 탐색부터는 단 한 번에 루트를 찾게 됩니다.
2-1. Union by Rank: 높이의 제어
또 다른 최적화는 Union by Rank(또는 Size)입니다. 두 집합을 합칠 때 항상 높이가 낮은 트리를 깊은 트리 아래에 붙여 전체 트리의 높이가 불필요하게 커지는 것을 막는 전략입니다. 경로 압축과 Union by Rank를 결합하면 유니온 파인드의 시간 복잡도는 $O(\alpha(N))$이 됩니다. $\alpha$는 아커만 함수의 역함수로, 실제 우주의 모든 데이터를 처리해도 5를 넘지 않는 상수 수준의 압도적인 성능입니다.
3. 유니온 파인드의 실전 활용과 MST
유니온 파인드는 그 자체로도 훌륭하지만, 최소 신장 트리(MST)를 구하는 크루스칼(Kruskal) 알고리즘에서 그 진가를 발휘합니다. 간선을 가중치 순으로 선택할 때마다 유니온 파인드를 사용하여 두 정점이 이미 같은 집합인지 확인하면, 그래프에 사이클(Cycle)이 생기는 것을 완벽하게 방지할 수 있습니다.
실무 응용 사례
- 네트워크 연결성 감시: 통신망 장애 발생 시 특정 구역 간의 연결 유무 실시간 판단.
- 이미지 분할(Image Segmentation): 픽셀 간의 유사성을 바탕으로 같은 객체 영역을 묶는 작업.
- 소셜 친구 추천: 지인의 지인을 찾아 그룹화하여 관심사 기반의 커뮤니티 생성.
# 최적화된 유니온 파인드(Union-Find) Python 구현
parent = [i for i in range(n + 1)]
def find(x):
# 경로 압축(Path Compression) 적용
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
rootA = find(a)
rootB = find(b)
if rootA != rootB:
# 간단한 합치기 전략 (작은 번호를 부모로)
if rootA < rootB:
parent[rootB] = rootA
else:
parent[rootA] = rootB
1. 원리: 데이터를 상호 배타적인 집합으로 관리하며 연결성을 빠르게 확인합니다.
2. 최적화: 경로 압축을 통해 트리를 평평하게 만들어 실질적인 상수 시간 속도를 보장합니다.
3. 활용: 크루스칼 알고리즘, 사이클 판별, 네트워크 그룹 관리 등 그래프 이론의 필수 도구입니다.