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

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

서로소 집합(Disjoint Set)들을 효율적으로 관리하는 자료구조로, 집합의 합치기(Union)와 원소가 속한 집합 찾기(Find) 연산을 거의 상수 시간에 수행

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

특징: 서로소 집합, Union·Find 연산, 거의 O(1), 경로 압축

구성요소: ① 부모 배열(parent) ② 랭크 배열(rank, 선택)

연산

• •Find(x): x가 속한 집합의 대표(루트) 찾기, 재귀
• •Union(x, y): x와 y가 속한 집합 합치기, 루트 연결

최적화

• •경로 압축(Path Compression): Find 시 거쳐간 노드들을 루트에 직접 연결, 트리 평탄화
• •랭크 기반 합치기(Union by Rank): 작은 트리를 큰 트리 아래 연결, 높이 최소화
• •크기 기반 합치기(Union by Size): 작은 집합을 큰 집합에 합침

시간 복잡도: O(α(n)) ≈ O(1) - α = 역 아커만 함수(사실상 상수)

공간 복잡도: O(n)

장점: 매우 빠른 연산(거의 O(1)), 단순한 구현, 동적 연결성

단점: 집합 분리 불가, 랜덤 접근 어려움

적용사례

• •크루스칼 MST(최소 스패닝 트리)
• •네트워크 연결성
• •이미지 세그멘테이션
• •친구 관계(소셜 네트워크)
• •사이클 검사(무방향 그래프)
• •동적 연결성 문제

비교: Union-Find(동적연결/O(α)) vs BFS/DFS(정적연결/O(V+E))

연관: 크루스칼, MST, 경로 압축, 서로소 집합