ds · 14

분리집합(Union-Find)

Union-Find그래프분리집합

"A와 B가 같은 그룹인가?"를 빠르게 답하고, 두 그룹을 하나로 합치는 일을 반복해야 할 때가 있습니다. 친구 관계의 연결 여부, 네트워크의 연결 요소, 그래프에서 사이클 판별이 그런 문제입니다. 분리집합(Disjoint Set, Union-Find)은 원소들을 서로 겹치지 않는 집합으로 나누어 두고, 원소가 속한 집합을 찾는 find와 두 집합을 합치는 union을 두 가지 최적화를 함께 쓰면 분할 상환으로 거의 상수 시간에 처리하는 자료구조입니다.

각 집합을 트리 하나로 표현하고, 원소마다 부모를 가리키는 parent 배열을 둡니다(크기 기준 합치기를 쓰면 루트별 크기 배열이 하나 더 필요합니다). 부모가 자기 자신인 노드가 집합의 대표(루트)입니다. find는 루트까지 올라가고, union은 한 루트를 다른 루트 밑에 붙입니다. 아무 최적화 없이 합치면 트리가 한 줄로 길어질 수 있어서, 크기 기준 합치기와 경로 압축이라는 두 가지 최적화를 함께 씁니다. 이 토픽에서는 같은 연산이 방식에 따라 트리 높이를 얼마나 바꾸는지 단계별로 봅니다.

핵심 개념

서로소 집합

모든 원소가 정확히 한 집합에만 속하도록 나눈 것입니다. 처음에는 원소마다 자기만 든 집합이고, union으로 합치면 집합의 개수가 하나씩 줄어듭니다.

핵심 개념

parent 배열

parent[i]는 i의 부모입니다. parent[i] == i이면 i가 루트이고, 두 원소의 루트가 같으면 같은 집합입니다. 포인터 없이 배열 하나로 숲을 표현합니다.

핵심 개념

find와 union

find(x)는 x에서 부모를 따라 루트까지 올라갑니다. union(a, b)는 두 루트를 찾아 하나를 다른 쪽 밑에 붙입니다. 두 루트가 이미 같으면 합칠 것이 없습니다.

핵심 개념

크기 기준 합치기

작은 트리의 루트를 큰 트리의 루트 밑에 붙입니다. 깊이가 늘어나는 쪽은 항상 작은 트리라서, 높이가 log2(n)을 넘지 않습니다. 크기 대신 높이의 상한인 랭크를 기준으로 삼는 방식도 있습니다.

핵심 개념

경로 압축

find가 루트를 찾으며 지나온 모든 노드의 부모를 루트로 바꿉니다. 트리가 납작해져서 같은 경로를 다시 걸을 때는 한 번에 루트에 닿습니다.

핵심 개념

역 아커만 함수

두 최적화를 함께 쓰면 연산 하나의 분할 상환 비용이 역 아커만 함수 α(n)에 비례합니다. α(n)은 현실적인 입력 크기에서 정의에 따라 4 또는 5 이하여서 사실상 상수로 봅니다.

최적화 없이는 find가 O(n)입니다 — 합치는 순서에 따라 트리가 한 줄로 이어지면 루트까지 올라가는 데 원소 수만큼 걸립니다.

두 최적화는 역할이 다릅니다 — 크기 기준 합치기는 트리가 높아지는 것을 미리 막고, 경로 압축은 이미 생긴 긴 경로를 find하면서 펴 줍니다.

집합 분리(쪼개기)는 지원하지 않습니다 — 합치기만 가능하고 한 번 합친 집합을 나누는 연산은 없습니다. 간선이 사라지는 문제에는 다른 방법이 필요합니다.

사이클 판별에 알맞습니다 — 간선을 하나씩 추가할 때 두 끝점의 루트가 이미 같으면 무방향 그래프에서 그 간선이 사이클을 만듭니다. 크루스칼 알고리즘이 이 성질을 씁니다.

이 시각화에서 확인할 것 — "기본 합치기"와 "크기 기준" 탭에서 같은 연산 5번의 결과 높이를 비교하고, "경로 압축" 탭에서 find가 지나간 노드가 루트에 붙는 과정을 STEP으로 확인하세요.

분리집합의 배경

트리로 집합을 표현하는 방식은 1964년 갤러(Galler)와 피셔(Fischer)가 동치 관계를 다루는 알고리즘으로 소개했고, 이후 크기·랭크 기준 합치기와 경로 압축의 효율이 분석되었습니다. 1975년 타잔(Tarjan)은 두 최적화를 함께 쓸 때 연산당 비용이 역 아커만 함수에 비례함을 보였습니다. 컴파일러의 타입 동치 판별, 이미지의 연결 영역 찾기, 그래프 알고리즘에서 널리 쓰입니다.

숫자로 확인하기

기본 합치기 — 원소 6개에서 union(1, 2), union(2, 3), ..., union(5, 6)을 첫 루트를 둘째 루트 밑에 붙이는 방식으로 실행하면 1 → 2 → 3 → 4 → 5 → 6 한 줄이 되어 높이 5입니다. find(1)은 부모를 5번 따라갑니다.

크기 기준 — 같은 연산을 크기가 작은 쪽을 큰 쪽 밑에 붙이는 방식으로 하면 루트 1 아래에 나머지 5개가 붙어 높이 1입니다. 원소 1000개에서도 높이는 999 대 1입니다.

경로 압축 — 한 줄짜리 트리에서 find(1) 한 번에 노드 1~4의 부모가 모두 루트 6으로 바뀝니다. 같은 find(1)은 5번에서 1번으로 줄어듭니다.

크루스칼 예시 — 정점 5개, 간선 7개에서 가중치가 작은 순으로 union이 성공한 간선 4개(2, 3, 4, 5)만 채택되어 합이 14입니다.

자주 하는 오해

find는 항상 O(1)이다 — 최적화가 없으면 O(n)입니다. 거의 상수라는 말은 두 최적화를 함께 쓴 분할 상환 비용을 가리킵니다.

경로 압축만 있으면 충분하다 — 경로 압축만 써도 분할 상환 O(log n)으로 좋아지지만, 크기 기준 합치기와 함께 써야 α(n) 수준이 됩니다.

루트가 항상 가장 작은 번호이다 — 크기 기준에서는 큰 트리의 루트가 대표가 되므로 번호와 무관합니다. 대표 원소가 필요하면 find의 결과를 쓰고, 번호가 중요하면 별도로 관리합니다.

합친 집합을 다시 나눌 수 있다 — 일반 구현에서는 한 번 합친 집합을 임의로 나눌 수 없습니다. 삭제나 분리가 필요한 문제는 롤백이 가능한 Union-Find와 오프라인 처리 같은 기법을 씁니다.

면접에서 이렇게 물어요

면접 질문

Union-Find는 어떤 자료구조인가요?

서로소 집합을 트리로 표현해, 원소가 속한 집합의 대표를 찾는 find와 두 집합을 합치는 union을 지원합니다. parent 배열(크기 기준 합치기를 쓰면 크기 배열 포함)로 구현하고, 같은 집합인지는 두 원소의 루트가 같은지로 판단합니다.

면접 질문

경로 압축과 크기 기준 합치기는 무엇인가요?

경로 압축은 find 중에 지나간 노드를 루트에 직접 연결하고, 크기 기준 합치기는 작은 트리를 큰 트리 밑에 붙입니다. 둘 다 트리를 낮게 유지해 find를 빠르게 합니다.

면접 질문

크루스칼에서 왜 Union-Find를 쓰나요?

간선을 추가할 때 두 끝점이 이미 같은 집합이면 사이클이 생기므로 건너뛰어야 합니다. 이 판별을 find로 거의 상수 시간에 하고, 채택한 간선은 union으로 합칩니다.

면접 질문

시간 복잡도는 어떻게 되나요?

두 최적화를 함께 쓰면 연산 m번의 총 비용이 O(m α(n))이고, α는 역 아커만 함수라서 사실상 상수입니다. 최적화가 없으면 find 한 번이 최악에 O(n)입니다.

실제 시스템에서는

그래프 알고리즘 — 크루스칼 최소 신장 트리, 연결 요소 개수 세기, 사이클 판별에 쓰입니다.

이미지 처리 — 인접한 같은 색 픽셀을 하나의 영역으로 묶는 연결 요소 라벨링에서 영역 합치기에 씁니다.

컴파일러 — 타입 추론에서 같다고 판명된 타입 변수들을 하나의 집합으로 묶는 단일화(unification) 구현에 쓰이기도 합니다.

연결 요소 관리 — 간선이 추가될 때 두 정점이 이미 연결됐는지 묻는 문제의 기본 도구입니다. 친구 관계나 장비 연결을 정점과 간선으로 모델링하는 문제가 그 예입니다.

함께 보면 좋은 토픽

최소 신장 트리 — 크루스칼 알고리즘이 Union-Find를 어떻게 쓰는지 봅니다.

그래프 — 연결 요소와 사이클이 나오는 그래프의 기본 개념을 봅니다.

트리 — 분리집합이 집합을 표현하는 데 쓰는 트리 구조를 봅니다.

시간 복잡도 — 분할 상환 분석과 점근 표기를 봅니다.

참고 자료

논문 — Galler, B. A. and Fischer, M. J., "An improved equivalence algorithm", Communications of the ACM 7(5), 1964

논문 — Tarjan, R. E., "Efficiency of a good but not linear set union algorithm", Journal of the ACM 22(2), 1975

교재 — CLRS, Introduction to Algorithms 4판, 19장 Data Structures for Disjoint Sets (3판은 21장)

학습 자료 — cp-algorithms Disjoint Set Union

Python — 경로 압축과 크기 기준 합치기

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))      # 처음에는 모두 자기가 루트
        self.size = [1] * n
        self.count = n                        # 집합의 개수

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:        # 경로 압축: 지나온 노드를 루트에 직접 연결
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                   # 이미 같은 집합
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                   # 큰 쪽이 루트가 되도록
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

uf = UnionFind(6)
print(uf.union(0, 1), uf.union(1, 2), uf.union(0, 2))   # True True False
print(uf.find(2) == uf.find(0), uf.find(3) == uf.find(0), uf.count)   # True False 4

parent 배열이 숲을 표현합니다. parent[i] == i이면 i가 루트이고, 아니면 i의 부모가 parent[i]입니다. find는 루트까지 올라간 뒤, 한 번 더 올라가며 지나온 노드의 부모를 루트로 바꿔 경로 압축을 합니다. union은 두 원소의 루트를 찾아, 이미 같으면 아무것도 하지 않고 False를 돌려줍니다. 다르면 크기가 작은 쪽 루트를 큰 쪽 루트 밑에 붙이고 크기를 더합니다. 이 반환값이 크루스칼 알고리즘에서 사이클 판별에 그대로 쓰입니다. 0, 1, 2를 합치면 세 번째 union(0, 2)는 이미 같은 집합이라 False입니다. 원소 6개에서 두 번 합쳤으므로 집합은 4개가 남고, 3은 아직 0과 다른 집합입니다.

Python — 합치기 방식에 따른 트리 높이

def height(parent):
    def depth(x):
        d = 0
        while parent[x] != x:
            x = parent[x]; d += 1
        return d
    return max(depth(i) for i in range(len(parent)))

def build(n, by_size):
    parent = list(range(n)); size = [1] * n
    def root(x):                          # 경로 압축 없는 find
        while parent[x] != x: x = parent[x]
        return x
    for i in range(n - 1):                # union(0,1), union(1,2), ... 순서
        ra, rb = root(i), root(i + 1)
        if by_size:
            if size[ra] < size[rb]: ra, rb = rb, ra
            parent[rb] = ra; size[ra] += size[rb]
        else:
            parent[ra] = rb                # 첫 루트를 둘째 루트 밑에
    return height(parent)

print(build(6, False), build(6, True))         # 5 1
print(build(1000, False), build(1000, True))   # 999 1

같은 순서의 union을 두 방식으로 실행해 트리 높이를 비교합니다. 첫 루트를 둘째 루트 밑에 붙이는 기본 방식은 한 줄로 이어져 원소 n개에서 높이가 n - 1까지 자랍니다. 시각화의 기본 합치기 탭이 보여 주는 높이 5와 같습니다. 크기 기준은 이 순서에서 큰 트리에 작은 트리를 계속 붙이므로 높이가 1에 머뭅니다. 원소가 1000개여도 999와 1의 차이가 납니다. 이 순서는 기본 방식에 가장 불리한 입력이어서 차이가 큽니다. 크기 기준의 높이는 어떤 순서에서도 log2(n) 이하라는 점이 보장입니다.

Python — 크루스칼 최소 신장 트리

def kruskal(n, edges):
    uf = UnionFind(n)
    total, used = 0, []
    for w, a, b in sorted(edges):         # 가중치가 작은 간선부터
        if uf.union(a, b):             # 서로 다른 집합일 때만 채택
            total += w
            used.append((a, b, w))
    return total, used

# (가중치, 정점, 정점)
edges = [(4, 0, 1), (8, 0, 2), (2, 1, 2), (6, 1, 3), (3, 2, 3), (5, 2, 4), (7, 3, 4)]
print(kruskal(5, edges))   # (14, [(1, 2, 2), (2, 3, 3), (0, 1, 4), (2, 4, 5)])

크루스칼 알고리즘은 간선을 가중치 순으로 훑으며, 두 끝점이 서로 다른 집합일 때만 간선을 고르고 두 집합을 합칩니다. 같은 집합이면 이미 연결된 두 정점을 또 잇는 것이어서 사이클이 생기므로 건너뜁니다. 이 판별과 합치기를 union 한 번이 모두 해 줍니다. 예에서 가중치 2, 3, 4, 5인 간선 4개가 채택되어 합이 14입니다. 가중치 6, 7, 8인 간선은 끝점이 이미 같은 집합이라 버려집니다. 연결 그래프이면 정점 V개에서 간선 V - 1개를 채택하고 끝납니다. 간선 정렬이 O(E log E)이고 union은 거의 상수 시간이어서 전체 시간은 정렬이 좌우합니다. 최소 신장 트리 자체는 알고리즘 과목의 MST 토픽에서 자세히 다룹니다.

Union-Find(분리 집합)의 두 가지 핵심 연산은?

이름에 연산이 그대로 들어 있습니다.

find는 원소가 속한 집합의 대표(루트)를 찾고, union은 두 원소가 속한 집합을 하나로 합칩니다. 서로소 집합의 관리에 쓰입니다.

경로 압축(Path Compression)의 효과는?

같은 경로를 다음에 또 걷지 않게 해줍니다.

find로 루트를 찾아가는 동안 거친 모든 노드의 부모를 루트로 바꿔 트리를 납작하게 만듭니다. 랭크(또는 크기) 기반 합치기와 함께 쓰면 연산이 거의 상수 시간에 가까워집니다.

크루스칼(Kruskal) 최소 신장 트리 알고리즘에서 Union-Find의 용도는?

이미 연결된 두 정점을 또 연결하면 사이클이 됩니다.

크루스칼은 가중치가 작은 간선부터 추가하되, 두 끝점이 이미 같은 집합이면 사이클이 생기므로 건너뜁니다. 이 판별을 find로, 합치기를 union으로 처리합니다.