카테고리 없음

유니온 파인드: 서로소 집합과 경로 압축 최적화 가이드

kguidebook0001 2026. 4. 8. 07:44

컴퓨터 알고리즘에서 데이터 그룹 간의 관계를 효율적으로 관리하는 문제는 매우 중요합니다. "A와 B가 같은 팀인가?", "두 정점이 서로 연결되어 있는가?"와 같은 질문에 실시간으로 답해야 할 때, 우리는 유니온 파인드(Union-Find)라고 불리는 서로소 집합(Disjoint Set) 자료구조를 사용합니다. 이 자료구조는 단순한 논리로 시작하지만, '경로 압축'과 '랭크 최적화'라는 기술이 더해지면 사실상 상수 시간에 가까운 압도적인 속도를 보여줍니다. 본 포스팅에서는 유니온 파인드의 내부 동작 원리와 성능 극대화 비결을 상세히 분석해 보겠습니다.

1. 유니온 파인드의 두 가지 핵심 연산: Find와 Union

유니온 파인드는 이름 그대로 두 가지 연산을 중심으로 동작합니다. 첫 번째는 특정 원소가 속한 집합(대표자)을 찾는 Find 연산이고, 두 번째는 서로 다른 두 집합을 하나로 합치는 Union 연산입니다. 이 구조를 구현하기 위해 우리는 각 노드가 부모 노드를 가리키는 트리 형태의 배열을 사용합니다.

1-1. 대표자(Root)를 통한 집합 식별

어떤 두 원소가 같은 집합에 속해 있는지 확인하는 방법은 매우 명확합니다. 두 원소에 대해 각각 Find 연산을 수행하여 얻은 루트 노드가 서로 같다면, 그들은 동일한 집합에 포함되어 있는 것입니다. 이처럼 루트 노드는 집합 전체를 대표하는 고유한 ID 역할을 수행하게 됩니다.

2. 성능의 혁신: 경로 압축(Path Compression)

기본적인 트리의 구조로 유니온 파인드를 구현하면, 트리가 한쪽으로 길게 치우치는 '편향 트리'가 될 위험이 있습니다. 이 경우 Find 연산의 복잡도가 $O(V)$까지 치솟아 효율성이 급격히 떨어집니다. 이를 방지하는 마법 같은 기술이 바로 경로 압축(Path Compression)입니다.

2-1. 재귀적으로 부모를 직접 연결하기

Find 연산을 수행할 때, 루트를 찾아 올라가는 과정에서 만나는 모든 노드들의 부모를 루트 노드로 직접 갱신해 버리는 것입니다. 이렇게 하면 다음에 동일한 노드에서 Find를 호출할 때 즉시 루트를 찾을 수 있게 됩니다. 이 과정을 거치면 트리의 높이가 획기적으로 낮아지며, 모든 노드가 루트에 직접 매달린 '평평한' 구조로 변모하게 됩니다.

3. 합치기 최적화: Union by Rank (or Size)

경로 압축과 함께 사용되는 또 다른 필수 최적화는 Union by Rank입니다. 두 집합을 합칠 때, 트리의 높이(Rank)가 낮은 트리를 높이가 높은 트리 아래에 붙이는 전략입니다. 이렇게 하면 전체 트리의 높이가 불필요하게 커지는 것을 방지할 수 있습니다. 경로 압축과 Union by Rank를 동시에 적용하면 유니온 파인드의 시간 복잡도는 $O(\alpha(V))$가 됩니다. 여기서 $\alpha$는 아커만 함수의 역함수로, 실제로는 5 이하의 상수에 수렴하는 수준입니다.

실무 활용 및 MST 알고리즘과의 연계

유니온 파인드는 그래프의 연결성 확인뿐만 아니라, 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘에서 사이클을 감지하는 핵심 부품으로 사용됩니다. 또한 이미지 프로세싱의 영역 분할, 네트워크 사용자 그룹 관리 등 집합 간의 관계가 중요한 모든 도메인에서 표준적으로 활용됩니다.


# 최적화된 유니온 파인드 구현 (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:
        # 간단한 Union 전략: 작은 인덱스를 부모로
        if rootA < rootB:
            parent[rootB] = rootA
        else:
            parent[rootA] = rootB
[유니온 파인드 핵심 요약]
1. 개념: 서로소 집합을 트리 구조로 관리하며 연결성 유무를 신속하게 판단합니다.
2. 최적화: 경로 압축을 통해 탐색 속도를, Union by Rank를 통해 트리 높이를 제어합니다.
3. 성능: 실질적으로 $O(1)$에 수렴하는 압도적인 속도를 자랑하며 크루스칼 알고리즘 등의 기반이 됩니다.