[알고리즘] 유니온-파인드(Union-Find)로 집합 관리하기

유니온-파인드의 동작 원리. find가 왜 재귀로 동작하는지, 경로 압축과 rank 기반 합치기가 실제로 어떻게 일어나는지 추적해봤다.

---

1. 유니온-파인드란?

핵심 아이디어

독립된 집합들을 합치고, 두 원소가 같은 집합인지 빠르게 확인하는 자료구조

여러 개의 독립된 집합이 있을 때 union으로 두 집합을 합치고, find로 두 원소가 같은 집합에 속하는지 확인하는 방식이다. 유니온-파인드 자체가 하나의 독립된 알고리즘이 아니라, find와 union이라는 두 연산으로 구성된 자료구조다.

기본 구조

def find(parents, x):
    if parents[x] != x:                          # 루트가 아니면
        parents[x] = find(parents, parents[x])   # 재귀로 루트 찾고 직접 연결
    return parents[x]                            # 루트 반환

def union(parents, rank, a, b):
    root_a = find(parents, a)   # a의 루트
    root_b = find(parents, b)   # b의 루트

    if root_a == root_b:        # 이미 같은 집합이면 스킵
        return

    if rank[root_a] < rank[root_b]:
        parents[root_a] = root_b
    elif rank[root_a] > rank[root_b]:
        parents[root_b] = root_a
    else:
        parents[root_b] = root_a
        rank[root_a] += 1

---

2. 배열로 표현한 집합

parents = [0, 1, 2, 3]처럼 인덱스가 노드 번호, 값이 부모 노드 번호를 의미한다. parents[i] == i이면 자기 자신이 루트, 즉 독립된 집합이다.

그림 1. 초기 상태 — 모두 독립

노드:    0    1    2    3
부모:    0    1    2    3   ← 전부 자기 자신이 부모 = 독립 집합

표 1. parents 배열과 집합 상태 변화

연산 parents rank 집합 상태

초기화	[0, 1, 2, 3]	[0, 0, 0, 0]	{0}, {1}, {2}, {3}
union(0, 1)	[0, 0, 2, 3]	[1, 0, 0, 0]	{0,1}, {2}, {3}
union(1, 2)	[0, 0, 0, 3]	[1, 0, 0, 0]	{0,1,2}, {3}

---

3. find — 루트를 찾는 과정

find는 딱 두 가지 일을 한다.

1. 루트를 찾아서 반환
2. 찾는 김에 경로 압축 — 거쳐간 모든 노드를 루트에 직접 연결

코드 1. 경로 압축이 적용된 find

def find(parents, x):
    if parents[x] != x:                          # ① 루트가 아니면
        parents[x] = find(parents, parents[x])   # ② 재귀로 루트 찾고, 바로 연결
    return parents[x]                            # ③ 루트 반환

핵심은 딱 한 줄이다.

parents[x] = find(parents, parents[x])

"내 부모를 직접 루트로 바꿔줘" 라는 뜻으로, 재귀가 풀리면서 거쳐간 모든 노드에 자동으로 적용된다.

그림 2. 경로 압축 전후 비교

압축 전: 0 ← 1 ← 2 ← 3   (find(3) 호출 시 4번 재귀)

find(3)
  parents[3]=2, 3≠2 → 재귀: find(parents, 2)
    parents[2]=1, 2≠1 → 재귀: find(parents, 1)
      parents[1]=0, 1≠0 → 재귀: find(parents, 0)
        parents[0]==0  →  return 0  ← 루트!
      parents[1] = 0  ← 압축
    parents[2] = 0  ← 압축
  parents[3] = 0  ← 압축

압축 후:    0
          / | \
         1  2  3   (이후 find(1), find(2), find(3) 모두 1번 재귀만 필요)

※ 경로 압축은 find를 호출할 때만 일어난다

parents[x]를 직접 읽는 것과 find(parents, x)를 호출하는 것은 다르다. parents[x]는 직속 부모를 가리킬 뿐이고, find를 한 번도 호출하지 않은 노드는 압축이 되어 있지 않을 수 있다. 따라서 같은 집합인지 확인할 때는 반드시 find를 사용해야 한다.

# ❌ 압축이 안 된 노드라면 틀린 결과
parents[3] == parents[0]   # 2 == 0 → False

# ✅ 항상 루트끼리 비교
find(parents, 3) == find(parents, 0)   # 0 == 0 → True

---

4. union — 두 집합을 합치는 과정

union은 세 단계로 동작한다.

1. find로 두 원소의 루트를 각각 구한다
2. 루트가 같으면 이미 같은 집합 → 스킵
3. rank가 작은 루트를 rank가 큰 루트 아래에 붙인다

rank란?

rank는 트리의 대략적인 높이다. 합칠 때 rank가 낮은 쪽을 높은 쪽 아래에 붙임으로써 트리가 불필요하게 깊어지는 것을 막는다.

그림 3. rank 기반 합치기

❌ rank 없이 합치기          ✅ rank 기반 합치기
      0                           0
      |                         / | \
      1                        1  2  3
      |
      2
      |
      3

코드 2. rank 기반 union

def union(parents, rank, a, b):
    root_a = find(parents, a)
    root_b = find(parents, b)

    if root_a == root_b:      # 이미 같은 집합 → 스킵
        return

    if rank[root_a] < rank[root_b]:
        parents[root_a] = root_b   # a의 루트를 b의 루트 아래로
    elif rank[root_a] > rank[root_b]:
        parents[root_b] = root_a   # b의 루트를 a의 루트 아래로
    else:
        parents[root_b] = root_a   # rank 같으면 아무거나, 단 rank +1
        rank[root_a] += 1

rank가 같을 때 어느 쪽을 루트로 해도 상관없는 이유: 유니온-파인드에서 중요한 건 루트가 누구냐가 아니라 같은 집합이냐 아니냐다. 어느 쪽을 루트로 해도 find(a) == find(b)의 결과는 동일하다.

root_a == root_b면 union을 하지 않는 이유: 이미 같은 집합이므로 트리 구조가 바뀔 게 없다. 실전에서는 이 조건이 사이클 감지(크루스칼 알고리즘)의 핵심 로직으로 활용된다.

---

5. 전체 흐름 추적

parents = [0, 1, 2, 3], rank = [0, 0, 0, 0]으로 시작하는 예시다.

데이터 1. union(0, 1) 흐름

root_a = find(parents, 0)
    parents[0] == 0  →  return 0
root_b = find(parents, 1)
    parents[1] == 1  →  return 1

root_a(0) != root_b(1)  →  union 진행
rank[0] == rank[1] == 0  →  else 분기
    parents[1] = 0
    rank[0] += 1

parents = [0, 0, 2, 3]
rank    = [1, 0, 0, 0]
집합: {0,1}, {2}, {3}

데이터 2. union(1, 2) 흐름

root_a = find(parents, 1)
    parents[1] = 0,  1 != 0
    parents[1] = find(parents, 0)
        parents[0] == 0  →  return 0
    parents[1] = 0  →  return 0   ← 경로압축 (이미 0이라 변화없음)

root_b = find(parents, 2)
    parents[2] == 2  →  return 2

root_a(0) != root_b(2)  →  union 진행
rank[0]=1 > rank[2]=0  →  elif 분기
    parents[2] = 0

parents = [0, 0, 0, 3]
rank    = [1, 0, 0, 0]
집합: {0,1,2}, {3}

---

6. 시간복잡도

경로 압축과 rank 기반 합치기를 함께 적용하면 시간복잡도가 사실상 O(1) 수준에 수렴한다.

표 2. 최적화 조합별 시간복잡도

find 방식 union 방식 find 시간복잡도

압축 없음	rank 없음	O(N)
경로 압축만	rank 없음	O(log N)
경로 압축	rank 기반	O(α(N)) ≈ O(1)

α(N)은 아커만 함수의 역함수로, 실제로 접할 수 있는 모든 N에 대해 4 이하의 값을 가진다. 사실상 상수로 봐도 무방하다.

---

7. 경로 압축과 유니온-파인드의 관계

경로 압축은 유니온-파인드의 find를 최적화하는 기법이고, rank 기반 합치기는 union을 최적화하는 기법이다. 두 기법 모두 없어도 유니온-파인드는 동작하지만, 함께 적용할 때 가장 효율적이다.

유니온-파인드 (자료구조)
├── find(parents, x)            ← 경로 압축으로 최적화
└── union(parents, rank, a, b)  ← rank 기반 합치기로 최적화

---

8. 실전 코드 (코딩테스트용)

코딩테스트에서는 parents를 전역변수로 빼서 매개변수를 줄이는 형태가 더 일반적이다.

코드 3. 코딩테스트 실전 템플릿

import sys
input = sys.stdin.readline

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
    elif rank[root_a] > rank[root_b]:
        parent[root_b] = root_a
    else:
        parent[root_b] = root_a
        rank[root_a] += 1

n = int(input())
parent = list(range(n))
rank = [0] * n

---

9. 재귀 vs 반복문 구현

find는 재귀 대신 반복문으로도 구현할 수 있다. 노드 수가 매우 많을 때 재귀 깊이 제한(Python 기본 1000)을 피하려면 반복문 방식이 안전하다.

코드 4. 반복문으로 구현한 find

def find(x):
    root = x
    while parent[root] != root:   # 루트 찾기
        root = parent[root]
    while parent[x] != root:      # 경로 압축
        parent[x], x = root, parent[x]
    return root

---

10. 유니온-파인드가 쓰이는 문제 유형

• 네트워크 연결 여부 — 두 노드가 같은 그룹인지 확인
• 사이클 감지 — 크루스칼 알고리즘에서 간선 추가 시 사이클 여부 판별
• 최소 신장 트리(MST) — 크루스칼 알고리즘의 핵심 자료구조