[알고리즘] Union-Find 유니온-파인드(Disjoint Set Union)

Union-Find(또는 Disjoint Set Union, DSU)는 그래프 알고리즘에서 서로소 집합(Disjoint Sets)을 관리하기 위해 사용되는 자료구조입니다. 이 알고리즘은 대표적으로 최소 스패닝 트리(MST) 알고리즘인 Kruskal's Algorithm에서 사용되며, 효율적으로 그래프의 연결성을 판단하거나 집합을 관리할 수 있습니다.

 

1. Union-Find란 무엇인가?

Union-Find는 다음 두 가지 연산을 빠르게 수행할 수 있도록 설계된 자료구조입니다.

1. Find(x): 원소 x가 속한 집합의 대표자(루트 노드)를 찾습니다.
2. Union(x, y): 원소 x와 y가 속한 두 집합을 하나로 합칩니다.

이 두 연산을 통해 집합을 동적으로 관리하며, 집합의 연결성을 확인할 수 있습니다. 예를 들어, 두 노드가 같은 집합에 속해 있는지 확인하는 것도 가능해집니다.

 

2. Union-Find의 주요 아이디어

Union-Find는 트리 구조를 사용하여 집합을 표현합니다. 각 원소는 부모 노드(parent)를 가리키며, 같은 집합에 속한 원소들은 루트 노드를 공유합니다. 이를 통해 연결성을 표현할 수 있습니다.

트리 구조의 예

다음은 5개의 원소(1, 2, 3, 4, 5)가 하나의 집합으로 묶여 있을 때의 트리 구조 예시입니다.

 

3. Union-Find의 핵심 최적화 기법

Union-Find는 두 가지 최적화 기법을 통해 매우 효율적으로 작동합니다:

(1) 경로 압축(Path Compression)

• Find(x) 연산을 수행할 때, 탐색 경로에 있는 모든 노드를 루트 노드에 직접 연결합니다.
• 이를 통해 트리의 깊이를 최소화하고, 이후 연산을 더욱 빠르게 만듭니다.

구현 예시 (경로 압축)

# Find 함수 구현 (경로 압축 포함)
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축
    return parent[x]

(2) 랭크 기반 병합(Rank-Based Union)

• Union(x, y) 연산에서 두 집합을 병합할 때, 항상 더 작은 트리를 큰 트리에 연결합니다.
• 트리의 높이를 최소화하여 효율성을 유지합니다.

구현 예시 (랭크 기반 병합)

# Union 함수 구현 (랭크 기반 병합 포함)
def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)

    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

 

4. Union-Find의 시간 복잡도

최적화된 Union-Find는 거의 상수 시간에 작동합니다. 정확히는 다음과 같은 시간 복잡도를 가집니다.

• Find:
• Union:

여기서는 역아커만 함수로, 매우 느리게 증가하는 함수입니다. 현실적으로는 거의 상수 시간으로 간주됩니다.

 

5. Union-Find 구현 예제

다음은 간단한 Union-Find 구현 예제입니다.

# Union-Find 기본 구현

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축
    return parent[x]

def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)

    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

# 초기화
n = 5  # 원소 개수
parent = list(range(n + 1))  # 각 원소는 자기 자신을 부모로 초기화
rank = [0] * (n + 1)  # 초기 랭크는 0

# Union 연산
union(parent, rank, 1, 2)
union(parent, rank, 2, 3)
union(parent, rank, 4, 5)

# Find 연산
print(find(parent, 1))  # 1과 연결된 대표 원소 출력
print(find(parent, 5))  # 5와 연결된 대표 원소 출력

 

6. Union-Find 활용 사례

Union-Find는 다음과 같은 문제를 해결하는 데 자주 사용됩니다.

1. 최소 스패닝 트리(MST): Kruskal's Algorithm에서 간선 선택 시 사이클을 감지하는 데 사용됩니다.
2. 사이클 탐지: 그래프에서 사이클 여부를 확인할 수 있습니다.
3. 동적 연결성: 그래프의 동적인 연결 상태를 관리할 수 있습니다.
4. 클러스터링: 데이터 클러스터링 문제를 해결할 수 있습니다.

 

7. Union-Find 활용 문제

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