서로소 집합 편집하기

서로소 집합(disjoint-set, 또는 disjoint-set data structure, disjoint-set forest)은 원소들이 겹치지 않는 여러 개의 집합으로 나뉘어 있을 때, 각 원소가 어떤 집합에 속해 있는지를 효율적으로 판별하고, 두 집합을 하나로 합치는 연산을 빠르게 수행할 수 있도록 하는 자료구조이다.
==개요==
서로소 집합 자료구조는 주로 집합 간의 결합(union)과 원소가 속한 집합의 대표 원소를 찾는(find) 연산을 수행하기 위한 용도로 사용된다. 이 자료구조는 대표적으로 [[유니온 파인드|'''유니온-파인드'''(union-find)]] 자료구조로도 알려져 있으며, 동적 연결성(dynamic connectivity)을 다루는 알고리즘, 예를 들어 [[크루스칼 알고리즘]]을 이용한 최소 신장 트리 구성 등에 핵심적으로 활용된다.
==연산==
서로소 집합 자료구조는 다음 세 가지 주요 연산을 지원한다.
*'''Make-Set(x)''': 원소 x만을 포함하는 새로운 집합을 생성한다.
*'''Find-Set(x)''': 원소 x가 속한 집합의 대표(루트) 원소를 반환한다.
*'''Union(x, y)''': x와 y가 속한 두 집합을 하나의 집합으로 합친다.
이 연산들은 다음 두 가지 최적화 기법을 통해 거의 상수 시간에 수행될 수 있다.
*'''경로 압축(Path Compression)''': Find 연산 시 경로 상의 모든 노드를 루트에 직접 연결하여 트리의 깊이를 줄인다.
*'''랭크 기준 합치기(Union by Rank)''': Union 연산 시 트리의 높이를 고려하여 낮은 랭크의 트리를 높은 랭크의 트리에 붙인다.
이 두 기법을 결합하면 각 연산의 시간 복잡도는 아커만 함수의 역함수에 비례하는 거의 상수 시간인 O(α(n))이 된다.
==파이썬 구현==
<syntaxhighlight lang="python">
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
</syntaxhighlight>
==응용==
서로소 집합 자료구조는 다음과 같은 분야에서 활용된다.
*최소 신장 트리 알고리즘 (예: 크루스칼 알고리즘)
*그래프에서의 연결 요소 탐색
*동적 집합 분할 문제
*등가 관계 추적
*퍼지 알고리즘(퍼지 집합 분류)
==같이 보기==
*[[그래프 이론]]
*[[크루스칼 알고리즘]]
*[[동적 연결성]]
*[[트리]]
*[[경로 압축]]
==참고 문헌==
*Thomas H. Cormen et al., ''Introduction to Algorithms'', MIT Press.
*Robert Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm", Journal of the ACM, 1975.
==각주==
[[분류:알고리즘]]
[[분류:자료 구조]]