CS학습2026년 8월 27일

Union-Find: 트리 구조로 집합을 합치고 찾는 상호배타적 집합(Disjoint Set)

Union-Find는 서로 겹치지 않는 여러 집합을 관리하면서 두 원소가 같은 집합에 속하는지 빠르게 확인하고, 두 집합을 하나로 합치는 연산을 제공하는 자료구조다. 경로 압축(Path Compression)과 랭크 기반 합치기(Union by Rank)를 함께 쓰면 각 연산이 사실상 상수 시간에 가까운 성능을 낸다. 네트워크 연결성 판단, 최소 신장 트리

송민성6분 읽기

1. 개념

Union-Find(합집합-찾기, Disjoint Set Union이라고도 부른다)는 서로 중복되지 않는 부분집합들의 모음을 관리하는 자료구조다. 이름 그대로 두 가지 핵심 연산을 지원한다.

Find: 특정 원소가 어느 집합에 속해 있는지 확인한다. 보통 그 집합을 대표하는 루트(root) 노드를 반환한다.
Union: 두 원소가 속한 두 집합을 하나로 합친다.

내부적으로는 각 집합을 트리로 표현한다. 트리의 루트가 그 집합의 대표자 역할을 하며, 두 원소의 루트가 같으면 같은 집합에 속한다고 판단한다.

2. 왜 사용하는가

그래프에서 "두 정점이 연결되어 있는가"를 반복해서 물어봐야 하는 상황을 생각해보자. 매번 BFS나 DFS로 그래프 전체를 탐색하면 간선이 추가될 때마다 비용이 크다. Union-Find는 연결 여부를 캐싱하듯 유지하면서 새로운 연결이 생길 때마다 집합을 합치는 방식으로 이 문제를 효율적으로 해결한다.

대표적인 활용 예:

그래프의 사이클 탐지 (간선을 추가하기 전에 두 정점이 이미 같은 집합인지 확인)
크루스칼(Kruskal) 알고리즘으로 최소 신장 트리 구하기
이미지에서 연결된 픽셀 영역(Connected Component) 찾기
네트워크에서 두 노드가 같은 클러스터에 속하는지 온라인으로 판별

3. 동작 원리

기본 구조

배열 parent에 각 원소의 부모를 저장한다. 처음에는 모든 원소가 자기 자신을 부모로 가진다(자기 자신이 루트인 상태).

text

parent = [0, 1, 2, 3, 4]  # 각 원소가 독립된 집합

Find 연산

루트를 찾을 때까지 부모를 따라 올라간다.

text

find(x):
    x의 부모가 자기 자신이 아니면
        find(parent[x])를 재귀 호출
    루트를 반환

이 과정을 최적화하지 않으면 트리가 한쪽으로 길게 늘어질 수 있고, 이 경우 Find 연산이 O(n)까지 느려진다. 이를 막기 위해 경로 압축(Path Compression)을 적용한다. Find를 수행하면서 방문한 모든 노드의 부모를 루트로 직접 연결해버리는 방식이다.

Union 연산

두 원소의 루트를 찾은 뒤, 한쪽 루트를 다른 쪽 루트의 자식으로 만든다. 이때 무작정 합치면 트리가 편향될 수 있으므로 Union by Rank(랭크 기반 합치기) 또는 Union by Size(크기 기반 합치기)를 사용한다. 트리의 높이(rank)나 크기(size)가 작은 쪽을 큰 쪽 밑에 붙여서 전체 트리 높이를 낮게 유지한다.

4. 코드 예제

python

class UnionFind:
    def __init__(self, n: int):
        # 처음에는 각 원소가 자기 자신을 부모로 갖는다
        self.parent = list(range(n))
        # 트리의 높이를 근사하는 랭크. 초기값은 모두 0
        self.rank = [0] * n
        # 현재 남아있는 독립 집합의 개수
        self.count = n

    def find(self, x: int) -> int:
        # 경로 압축: 탐색 경로상의 모든 노드를 루트에 직접 연결
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x, root_y = self.find(x), self.find(y)

        if root_x == root_y:
            return False  # 이미 같은 집합이면 합치지 않는다

        # Union by Rank: 랭크가 낮은 트리를 랭크가 높은 트리 밑에 붙인다
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


# 사용 예: 사이클 탐지
if __name__ == "__main__":
    uf = UnionFind(5)
    edges = [(0, 1), (1, 2), (2, 3), (3, 0)]  # 마지막 간선이 사이클을 만든다

    for a, b in edges:
        if uf.connected(a, b):
            print(f"간선 ({a}, {b})은 사이클을 만듭니다")
        else:
            uf.union(a, b)
            print(f"간선 ({a}, {b})을 연결했습니다")

    print(f"남은 집합 개수: {uf.count}")

실행 결과:

text

간선 (0, 1)을 연결했습니다
간선 (1, 2)을 연결했습니다
간선 (2, 3)을 연결했습니다
간선 (3, 0)은 사이클을 만듭니다
남은 집합 개수: 2

5. 시간 복잡도 또는 성능 특성

| 조건 | Find/Union 시간복잡도 | |---|---| | 최적화 없음 | O(n) (최악의 경우 트리가 사슬 형태) | | 경로 압축만 적용 | O(log n) 상각(amortized) | | 랭크/크기 기반 합치기만 적용 | O(log n) | | 경로 압축 + 랭크 기반 합치기 모두 적용 | O(α(n)) — 상각 시간 |

여기서 α(n)은 아커만 함수(Ackermann function)의 역함수로, 우주에 존재하는 원자 수보다 큰 n에 대해서도 4를 넘지 않는다. 실무적으로는 O(1)에 가깝다고 봐도 무방하다. 정확히는 O(1)이 아니라 "매우 느리게 증가하는 함수"라는 점은 구분해서 알아두는 게 좋다.

공간복잡도는 O(n)이다. parent 배열과 rank(또는 size) 배열을 각각 n 크기로 유지한다.

6. 실무 사용 사례

크루스칼 알고리즘: 간선을 가중치 순으로 정렬한 뒤, Union-Find로 사이클 여부를 확인하면서 최소 신장 트리를 구성한다.
소셜 네트워크 분석: 사용자 간 팔로우/친구 관계를 간선으로 보고, 같은 커뮤니티(연결 요소)에 속하는 사용자를 빠르게 그룹핑한다.
이미지 처리: 픽셀을 노드로 보고 인접한 같은 색 픽셀을 합치면서 연결된 영역(블롭)을 검출한다. OpenCV의 connectedComponents 계열 함수 내부에서 유사한 개념이 쓰인다.
컴파일러의 타입 추론: Hindley-Milner 타입 시스템에서 타입 변수 간 동일성(unification)을 관리할 때 Union-Find 구조를 활용한다.
분산 시스템의 장애 도메인 그룹핑: 같은 랙(rack)이나 같은 가용 영역(AZ)에 속한 노드를 동적으로 그룹화할 때 응용할 수 있다.

7. 주의할 점

경로 압축을 재귀로 구현하면 스택 오버플로우 위험이 있다. 원소 개수가 매우 많은 경우(수백만 단위) 반복문 기반으로 구현하거나 재귀 깊이 제한을 늘려야 한다.
Union by Rank와 Union by Size를 혼동하지 말 것. Rank는 트리의 높이를 근사한 값이고, 경로 압축이 일어나면 실제 높이와 rank 값이 정확히 일치하지 않게 된다. 그래도 알고리즘 정당성에는 문제가 없지만, "rank가 실제 높이다"라고 오해하면 안 된다.
원소를 집합에서 제거하는 연산은 기본 Union-Find로 지원하지 않는다. 삭제가 필요하면 별도의 자료구조(예: 오프라인으로 역순 처리)를 고려해야 한다.
초기화 시점에 원소 개수를 미리 알아야 한다. 동적으로 원소가 계속 추가되는 상황이라면 배열 크기를 늘리는 로직을 추가로 구현해야 한다.
두 집합의 대표자(루트)가 무엇을 의미하는지는 애플리케이션에 따라 정의해야 한다. 예를 들어 "각 집합의 대표값 중 최댓값" 같은 부가 정보를 유지하려면 union 연산에서 추가 로직을 넣어야 한다.

8. 핵심 정리

Union-Find는 상호배타적인 집합들을 트리로 표현하고, Find(루트 찾기)와 Union(집합 합치기) 두 연산으로 관리하는 자료구조다.
경로 압축과 랭크(또는 크기) 기반 합치기를 함께 적용하면 각 연산이 상각 O(α(n))으로 사실상 상수 시간에 동작한다.
사이클 탐지, 최소 신장 트리, 연결 요소 검출처럼 "연결성"을 반복해서 물어보는 문제에 적합하다.
원소 삭제는 지원하지 않으며, 재귀 구현 시 스택 오버플로우에 주의해야 한다.