🧩 유니온 파인드 (Disjoint Set) - 분리 집합 자료구조 완전 정리

---

✅ 유니온 파인드란?

유니온 파인드(Disjoint Set)는
여러 개의 원소를 겹치지 않는 그룹(집합)으로 나누고,
어떤 두 원소가 같은 집합에 속해 있는지 빠르게 판단할 수 있게 해주는 자료구조이다.

---

✅ 자료구조인가? 알고리즘인가?

유니온 파인드는 기본적으로는 자료구조지만,
알고리즘적 최적화 기법이 핵심인 구조이기 때문에
실전에서는 "자료구조적인 알고리즘"으로 취급되기도 한다.

📦 자료구조적 특징

• parent[] 배열로 트리 기반의 집합 구조 유지
• rank[] 또는 size[]로 트리 높이 관리

🧠 알고리즘적 특징

• 경로 압축 (Path Compression): find 연산 최적화
• 랭크 기반 병합 (Union by Rank): union 연산 최적화
  → 이 두 가지를 결합하면 거의 O(1)에 가까운 속도를 얻을 수 있다.

---

✅ 핵심 연산 두 가지

연산	설명
find(x)	x가 속한 집합의 대표(루트)를 찾음
union(a, b)	a와 b가 속한 두 집합을 합침

---

✅ 유니온 파인드 기본 구현 (최적화 없이)

# 초기화
n = 5
parent = [i for i in range(n)]

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

def union(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a != root_b:
        parent[root_b] = root_a

---

✅ 경로 압축 (Path Compression)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 루트를 한 번에 당겨오기
    return parent[x]

🔍 이 최적화를 적용하면 트리 높이가 매우 낮아지고,
탐색 속도가 O(α(N)) 수준으로 향상된다.

---

✅ 랭크 기반 병합 (Union by Rank)

rank = [1] * n

def union(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a == root_b:
        return
    if rank[root_a] < rank[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_b] = root_a
        if rank[root_a] == rank[root_b]:
            rank[root_a] += 1

🔍 항상 더 낮은 트리를 더 높은 트리 아래에 붙여서
트리 깊이가 불필요하게 커지는 것을 방지한다.

---

✅ 최적화 버전 전체 예제

n = 5
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(a, b):
    root_a = find(a)
    root_b = find(b)
    if root_a == root_b:
        return
    if rank[root_a] < rank[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_b] = root_a
        if rank[root_a] == rank[root_b]:
            rank[root_a] += 1

# 집합 합치기
union(0, 1)
union(1, 2)
union(3, 4)

# 같은 집합 여부 확인
print(find(0) == find(2))  # True
print(find(0) == find(4))  # False

---

✅ 시간복잡도

연산	시간복잡도 (최적화 적용 시)
find	O(α(N))
union	O(α(N))

※ α(N): 역 아커만 함수, 실질적으로 거의 O(1)처럼 동작함.

---

✅ 대표적인 응용 분야

• 사이클 판별 (두 노드가 이미 같은 집합이면 사이클)
• MST (크루스칼 알고리즘) 구현 시 필수
• 네트워크 연결성 판별
• 무방향 그래프의 연결 요소 처리
• 다양한 코테 문제에서 효율적인 그룹 관리 용도

---

🎯 마무리 요약

• 유니온 파인드는 서로 다른 집합을 빠르게 합치고,
  같은 집합인지 빠르게 판별할 수 있는 구조다.
• 핵심 연산은 find, union이고,
  경로 압축 + 랭크 기반 병합을 반드시 적용해야 실전 성능이 극대화된다.
• MST, 사이클 판별, 집합 분리 문제 등
  실전 알고리즘 문제에서 매우 자주 등장하는 필수 알고리즘이다.