한양과기고 에듀테크 수업도구 대시보드

유니온-파인드 (Union-Find / 서로소 집합)

여러 원소를 겹치지 않는 그룹(서로소 집합)으로 관리하면서 두 가지 질문에 빠르게 답하는 자료구조다. find(x) — x가 속한 그룹의 대표(루트)는? union(a, b) — a와 b의 그룹을 하나로 합쳐라. 각 그룹을 부모 포인터로 이어진 트리로 표현하고, union by rank(낮은 트리를 높은 트리 밑에 붙이기)와 path compression(찾은 경로의 노드를 루트에 바로 연결)을 함께 쓰면 연산 한 번이 사실상 상수 시간 O(α(n)) 에 끝난다.

서로소 집합 시뮬레이터 (원소 0~9)

union( , ) find( )

union by rank path compression

두 원소를 골라 합치기 를 눌러 그룹을 만들어 보세요.

분리된 그룹 수

가장 깊은 트리 높이

마지막 find 경로 길이

–

핵심 코드 (경로 압축 + union by rank)

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])  # path compression
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False          # 이미 같은 그룹 (사이클!)
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra                    # 항상 rank 큰 쪽을 부모로
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

왜 트리인가? 각 원소가 "내 부모는 누구" 하나만 기억하면, 루트까지 따라 올라가서 그룹 대표를 알 수 있다.
union by rank/size 없이 순진하게 합치면 트리가 한 줄로 길어져 find 가 O(n) 까지 나빠진다.
path compression: 한 번 루트까지 올라가 본 김에, 경로에 있던 노드들을 전부 루트 밑으로 옮겨 다음 탐색을 짧게 만든다.
둘을 같이 쓰면 연산당 평균 비용이 O(α(n)) — α는 아커만 함수의 역함수로, 현실적인 n에서는 4 이하 (사실상 상수).

어디에 쓰나

크루스칼(Kruskal) 최소 신장 트리: 간선을 가중치 순으로 보며, 두 끝점이 find 로 다른 그룹일 때만 채택하고 union. 같은 그룹이면 사이클이 생기므로 건너뛴다.
그래프 연결 요소 / 사이클 판정: 간선을 하나씩 union 하다가 union 이 False 를 반환하면 그 간선이 사이클을 만든다는 뜻.
네트워크 연결성: "컴퓨터 A와 B가 같은 네트워크에 속하는가?" → find(A) == find(B).
이미지 라벨링·미로·게임 맵: 인접한 같은 색 픽셀을 union 해서 덩어리(region) 개수 세기.
오프라인 쿼리 처리: 간선 추가만 있는 동적 연결성 문제, 백준 등 PS에서 매우 자주 등장.

방법	find 한 번 비용	비고
순진한 트리	O(n)	한 줄로 늘어질 수 있음
+ union by rank	O(log n)	트리 높이 제한
+ path compression	O(α(n)) ≈ O(1)	사실상 상수