Union-Find (유니온 파인드, Disjoint Set)

Union-Find (유니온 파인드, Disjoint Set)

분리 집합(Disjoint Set)을 효율적으로 관리하는 자료구조로 Union(합치기)과 Find(찾기) 연산을 거의 상수 시간(O(α(n)), α=아커만 역함수)에 수행하며 경로 압축과 랭크 기반 합치기 최적화 활용

목적: 집합 관리, 연결 요소 판단, 사이클 검사, MST

특징: 거의 상수 시간, 경로 압축, 랭크/크기 기반 합치기, 트리 구조

연산

• •Make-Set(x): 원소 x를 포함하는 집합 생성, parent[x] = x
• •Find(x): x가 속한 집합의 대표 원소(루트) 반환, 경로 압축 적용
• •Union(x, y): x와 y가 속한 집합 합치기, 랭크/크기 기반

경로 압축(Path Compression): Find 시 경로의 모든 노드를 루트에 직접 연결, 트리 평탄화

랭크 기반 합치기(Union by Rank): 랭크(트리 높이) 작은 트리를 큰 트리에 붙임, 높이 증가 최소화

크기 기반 합치기(Union by Size): 크기 작은 집합을 큰 집합에 붙임, 유사 효과

시간 복잡도: O(α(n)) 거의 상수, α(n)=아커만 역함수 ≈ 4 (실용적으로)

공간 복잡도: O(n)

장점: 매우 빠름(거의 상수), 단순 구현, 효율적

단점: 집합 분리 불가, 원소 삭제 어려움, 랭크 관리 필요

적용사례: Kruskal MST, 사이클 검사, 연결 요소, 이미지 분할, 네트워크 연결성

비교: Union-Find(거의상수/단순) vs DFS/BFS(선형/유연) vs 비트마스크(작은n)

연관: Kruskal, MST, 사이클 검사, 경로 압축, 분리 집합