[ 유니온 파인드 ] 유니온 파인드 이론 정리

유니온 파인드(또는 Disjoint Set Union, DSU)는 서로소 집합(Disjoint Set)을 다룰 때 사용하는 자료구조다. 주로 무방향 그래프의 사이클 판별이나 크루스칼 알고리즘을 활용한 최소 신장 트리(MST) 문제에서 자주 사용된다.

 

1. 유니온 파인드의 핵심 아이디어

• 여러 개의 원소가 있을 때, 이들을 서로소 집합(즉, 겹치지 않는 집합)으로 분리하여 관리한다.
• 두 원소가 같은 집합에 속하는지 확인하거나, 두 집합을 합치는 연산을 지원한다.
• 대표적으로 사용하는 연산은 아래 두 가지다:
  • find(x) : 원소 x가 속한 집합의 루트(대표값)를 찾는다.
  • union(x, y) : 원소 x, y가 속한 두 집합을 하나로 합친다.

 

2. 기본 구현

 

# 부모 테이블 초기화
parent = [i for i in range(n + 1)]

# 루트 노드 찾기
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

# 두 집합 합치기
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        if root_x < root_y:
            parent[root_y] = root_x
        else:
            parent[root_x] = root_y

 

 

 

 

3. 경로 압축 (Path Compression)

• find() 함수를 재귀적으로 호출하면서 루트 노드를 찾을 때, 중간 노드들을 루트에 바로 연결시킨다.
• 이렇게 하면 find의 시간 복잡도가 거의 O(1)에 수렴하게 된다.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

 

4. 합치기 최적화 (Union by Rank / Size)

• 집합을 합칠 때, 작은 집합을 큰 집합 밑으로 붙이는 전략.
• 일반적으로는 생략해도 괜찮지만, 성능을 더 높이고 싶다면 사용한다.