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

1. 유니온-파인드란?

유니온-파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set) 을 관리하는 자료구조로, 대표적으로 그래프에서 사이클 판별, 네트워크 연결성 검사, 최소 신장 트리(MST) Kruskal 알고리즘 등에 활용됩니다.

 

이 알고리즘은 다음 두 가지 핵심 연산을 수행합니다.

• Find 연산: 특정 원소가 속한 집합(루트 노드)을 찾는 연산
• Union 연산: 두 개의 집합을 하나로 합치는 연산

최적화 기법을 적용하면 매우 효율적으로 동작하여 거의 상수 시간(α(n), 아커만 함수의 역함수 수준) 에 연산을 수행할 수 있습니다.

 

---

 

2. 기본적인 유니온-파인드 구현

유니온-파인드는 보통 배열을 사용하여 트리 형태로 집합을 표현합니다.
각 원소는 부모 노드를 가리키며, 루트 노드는 자기 자신을 가리킵니다.

 

기본적인 코드 구현 (Python)

# 부모 노드를 저장하는 배열
parent = []

def init(n):
    global parent
    parent = [i for i in range(n)]  # 자기 자신을 부모로 설정

def find(x):
    if parent[x] != x:
        return find(parent[x])  # 재귀적으로 루트 노드 찾기
    return x

def union(x, y):
    rootX = find(x)
    rootY = find(y)
    
    if rootX != rootY:
        parent[rootY] = rootX  # y의 루트를 x의 루트로 변경

위 코드는 기본적인 유니온-파인드 동작을 수행하지만, 최적화 기법을 적용하지 않아 효율적이지 않습니다.

 

---

 

3. 경로 압축(Path Compression) & 랭크 기반 유니온(Rank Union)

유니온-파인드의 성능을 최적화하기 위해 두 가지 기법을 활용합니다.

 

1) 경로 압축(Path Compression)

• find(x) 연산을 수행할 때, 재귀적으로 루트 노드를 찾으며 부모 노드를 루트로 설정 합니다.
• 이를 통해 트리의 높이를 낮추어 이후의 find 연산 속도를 대폭 개선 할 수 있습니다.

 

2) 랭크 기반 유니온(Rank Union)

• union(x, y) 연산에서 더 작은 트리를 큰 트리에 연결 하여 트리의 높이를 최소화합니다.
• 높이가 낮은 트리를 높은 트리에 붙이면 전체 트리의 깊이가 증가하는 것을 방지할 수 있습니다.

 

최적화된 유니온-파인드 코드 (Python)

# 부모와 랭크를 저장하는 배열
parent = []
rank = []

def init(n):
    global parent, rank
    parent = [i for i in range(n)]
    rank = [1] * n

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

def union(x, y):
    rootX = find(x)
    rootY = find(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  # 같은 높이면 루트의 랭크 증가

위 코드에서는 경로 압축 을 통해 find 연산을 최적화하고, 랭크 기반 유니온 을 활용하여 트리의 깊이를 최소화했습니다.

 

---

 

4. 유니온-파인드의 시간 복잡도 분석

유니온-파인드는 최적화 기법을 적용했을 때 거의 O(1) 수준의 시간 복잡도 로 동작합니다.

• 일반적인 트리 구조에서 find 연산의 시간 복잡도는 O(log N) 이지만, 경로 압축을 적용하면 거의 O(α(N)) (아커만 함수의 역함수) 수준으로 줄어듭니다.
• union 연산은 두 개의 루트를 찾고 합치는 연산으로, find 연산이 포함되지만 랭크 기반 최적화 로 인해 거의 O(1) 시간에 수행됩니다.

실질적으로 유니온-파인드의 시간 복잡도는 O(α(N)) 으로 간주되며, 매우 빠르게 동작 합니다.

 

---

 

5. 유니온-파인드의 활용 예시

유니온-파인드는 다양한 그래프 문제에서 활용됩니다.

 

1) 사이클 판별 (Cycle Detection)

그래프에서 사이클이 존재하는지 판별할 때 유니온-파인드를 사용할 수 있습니다.

• 간선을 하나씩 확인하면서 find(x) == find(y) 라면 사이클이 존재함을 의미합니다.

# 그래프의 간선 리스트
edges = [(0, 1), (1, 2), (2, 0), (2, 3)]

init(4)
cycle = False
for u, v in edges:
    if find(u) == find(v):
        cycle = True
        break
    union(u, v)

print("사이클 발생" if cycle else "사이클 없음")

 

2) 크루스칼 알고리즘 (MST)

최소 신장 트리(MST)를 구하는 Kruskal 알고리즘 에서 유니온-파인드 를 활용합니다.

• 간선을 가중치 기준으로 정렬한 뒤, union 연산을 수행하여 최소 비용 신장 트리를 구성합니다.

 

3) 네트워크 연결성 검사

네트워크가 서로 연결되어 있는지 확인 하는 문제에서도 유니온-파인드를 사용할 수 있습니다.

 

---

 

6. 배운점

• 유니온-파인드(Union-Find) 는 서로소 집합(Disjoint Set) 을 관리하는 자료구조입니다.
• 핵심 연산은 find(루트 찾기) 와 union(집합 합치기) 입니다.
• 경로 압축(Path Compression) 및 랭크 기반 유니온(Rank Union) 을 적용하면 거의 O(1) 시간에 동작합니다.
• 그래프 사이클 판별, MST(Kruskal), 네트워크 연결 문제 등에 널리 활용됩니다.