DisjointSet

DisjointSet (서로소 집합, Union-Find) (2026-08-05)

특징

• 교집합이 없는 서로소 집합(disjoint set) 들을 다루는 자료구조 (= Union-Find = DSU)
• 두 집합을 합치는 union, 원소가 속한 집합의 대표값을 찾는 find 를 매우 빠르게 수행
• 한 집합은 하나의 대표원소(루트) 로 표현 → 나머지 원소는 루트로 가는 경로를 갖는 트리로 저장
• 전체 구조는 트리 하나가 아니라 여러 트리의 모음(숲, forest) → 남은 서로 다른 루트의 개수 = 그룹 개수
• 여기서 "서로소"는 집합론적 서로소(disjoint, 교집합 없음) 이지, 수론적 서로소(coprime, 최대공약수 1)가 아님

구조 (정수 배열 버전)

• parent[i] : 원소 i의 부모. 원소 i의 정보는 항상 i번 칸에 저장 (원소 = 인덱스로 설계)
  • parent[i] == i 이면 i가 루트
  • union은 부모 값만 바꿀 뿐, "i가 i번 칸에 산다"는 사실은 안 바뀜
• rank[i] : 트리의 높이(상한). 배열엔 모두 값이 있지만 의미 있는 건 루트의 rank뿐 (자식 rank는 방치된 죽은 값)
• count : 현재 그룹(집합) 개수. 전체에 하나뿐인 변수
• 초기 상태: parent[i] = i, rank[i] = 0, count = n → 모두가 혼자인 서로소 집합 n개

핵심 개념

• find: 부모가 자기 자신(루트)일 때까지 거슬러 올라가 대표값을 찾음
• union: 두 원소의 루트를 먼저 구한 뒤, 루트끼리 rank를 비교해 합침
  • if (rootA == rootB) return; → 이미 같은 집합이면 아무것도 안 함 (없으면 count가 틀어짐 / 사이클 판별에도 이 조건 사용)
  • rank가 높은 루트 밑에 낮은 트리를 붙임 (전체 높이 안 커짐)
  • rank가 같을 때만 아무 쪽에 붙이고 그 루트의 rank++ (높이가 한 층 늘어남)
  • 실제로 합쳐질 때만 count--

두 가지 최적화

• 최적화 1 — Union by Rank (높이 기준 합치기)
  • 높은 트리에 낮은 트리를 붙여 전체 높이가 커지는 걸 방지 → find가 O(log n)
• 최적화 2 — Path Compression (경로 압축)
  • parent[x] = find(parent[x]) — 루트를 찾으며 경로상의 모든 노드를 루트에 직접 연결
  • return find(...) 이 아니라 대입(parent[x] =) 이 핵심 → 다음 find부터 한 번에 도착
  • 예: [1,1,2,3] 일자 트리에서 find(4) 한 번 → [1,1,1,1] 로 납작해짐
• 두 최적화를 함께 쓰면 find/union이 사실상 상수 O(α(n)) (α = 아커만 역함수, 현실 입력에서 4 이하)

시간 복잡도

연산	최적화 없음	Union by Rank	Rank + Path Compression
find	O(n)	O(log n)	O(α(n)) ≈ O(1)
union	O(n)	O(log n)	O(α(n)) ≈ O(1)

주요 메서드

메서드	설명	시간복잡도
find(int x)	x의 대표값(루트) 반환 + 경로 압축	O(α(n))
union(int a, int b)	a, b가 속한 두 집합을 합침	O(α(n))
isSameSet(int a, int b)	두 원소가 같은 집합인지 확인	O(α(n))
getCount()	현재 그룹(집합) 개수 반환	O(1)