서로소 집합

서로소 집합(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))이 된다.

파이썬 구현

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

응용

서로소 집합 자료구조는 다음과 같은 분야에서 활용된다.

• 최소 신장 트리 알고리즘 (예: 크루스칼 알고리즘)
• 그래프에서의 연결 요소 탐색
• 동적 집합 분할 문제
• 등가 관계 추적
• 퍼지 알고리즘(퍼지 집합 분류)

같이 보기

• 그래프 이론
• 크루스칼 알고리즘
• 동적 연결성
• 트리
• 경로 압축

참고 문헌

• 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.