유니온 파인드
개요
유니온 파인드(union–find) 또는 서로소 집합 자료구조(disjoint-set data structure)는 원소들을 겹치지 않는 집합들로 나누어 두고, 두 집합을 하나로 합치거나(union) 두 원소가 같은 집합에 속해 있는지(find) 판별한다. 처음에는 각 사람이 1인 모임으로 시작해 모임끼리 계속 합쳐지는 상황에서, 합칠 때마다 모든 구성원의 소속 번호를 일일이 고쳐 쓰는 대신 각 모임의 대표 원소끼리만 부모 포인터로 연결하는 방식이다.
연혁
Bernard A. Galler와 Michael J. Fischer는 1964년 논문 「An Improved Equivalence Algorithm」에서 FORTRAN 프로그램의 EQUIVALENCE 선언문을 처리하기 위해 부모 포인터 트리로 동치류를 표현하는 알고리즘을 발표했다.1
이후 작은 트리를 큰 트리 밑에 붙이는 가중 병합(weighted union)과 탐색 경로상의 노드를 루트에 직접 연결하는 경로 압축(collapsing rule)이 결합되면서 시간 복잡도 규명이 난제로 떠올랐다. John E. Hopcroft와 Jeffrey D. Ullman이 1973년 반복 로그 함수 상한을 증명했고, 1975년 Robert E. Tarjan이 역 아커만 함수 을 도입해 이 상한이자 동시에 하한(tight bound)임을 증명했다. 이어 1989년 Michael L. Fredman과 Michael E. Saks는 셀 프로브 모델(cell-probe model)에서 서로소 집합을 다루는 어떤 자료구조도 연산당 분할상환 시간을 피할 수 없음을 보였다.2
크기 기준 병합과 경로 압축
각 원소 는 부모 를 가리키고, 집합의 대표인 루트만 로 자기 자신을 가리킨다. find(x)는 부모 포인터를 따라 루트를 찾는다. 두 원소의 루트가 같으면 같은 집합이다. 다만 루트 번호는 트리 균형에 따라 병합 시 바뀔 수 있는 내부 식별자이므로, 집합에 고정된 업무상 이름이나 속성이 필요하다면 루트를 키로 삼아 별도 테이블에 보관해야 한다.
아무 기준 없이 한 루트를 다른 루트 밑에 붙이면 트리가 한 줄로 길어져 탐색이 까지 퇴화한다. union(a, b)에서 원소 수가 적은 트리의 루트를 큰 트리의 루트 밑에 붙이면(크기 기준 병합), 어떤 노드의 깊이가 늘어날 때마다 그 노드가 속한 집합의 크기가 최소 두 배로 커지므로 경로 압축 없이도 트리의 최대 높이가 이하로 묶인다. 여기에 find(x)가 루트까지 올라가며 거친 모든 노드의 부모를 루트로 곧바로 바꿔치기하는 경로 압축을 더하면, 개 원소에서 번 연산을 수행하는 분할상환 시간은 다음과 같다.
실행 예제
원소 0부터 4까지 다섯 개로 시작해 {0, 1}과 {2, 3}을 각각 묶은 뒤 두 집합을 다시 합치고, 4는 홀로 남겨 둔다. 이미 같은 집합에 속한 두 원소에 union을 호출하면 false를 반환해 실제로 분할이 합쳐졌는지 구별한다.
class UnionFind {
private parent: number[];
private sizes: number[];
constructor(count: number) {
this.parent = Array.from({ length: count }, (_, index) => index);
this.sizes = new Array<number>(count).fill(1);
}
find(value: number): number {
let root = value;
while (root !== this.parent[root]) root = this.parent[root]!;
while (value !== root) {
const next = this.parent[value]!;
// 루트를 찾으며 지나온 모든 노드를 루트 직속 자식으로 물린다(경로 압축).
this.parent[value] = root;
value = next;
}
return root;
}
union(a: number, b: number): boolean {
let rootA = this.find(a);
let rootB = this.find(b);
if (rootA === rootB) return false;
// 원소 수가 적은 트리를 큰 트리 루트 밑에 붙여 높이 증가를 억제한다.
if (this.sizes[rootA]! < this.sizes[rootB]!) [rootA, rootB] = [rootB, rootA];
this.parent[rootB] = rootA;
this.sizes[rootA] = this.sizes[rootA]! + this.sizes[rootB]!;
return true;
}
sizeOf(value: number): number {
return this.sizes[this.find(value)]!;
}
}
const groups = new UnionFind(5);
groups.union(0, 1);
groups.union(2, 3);
groups.union(1, 2);
console.log(groups.find(0) === groups.find(3));
console.log(groups.find(0) === groups.find(4));
console.log(groups.union(0, 3));
console.log(groups.sizeOf(3));true
false
false
40과 3은 같은 대표를 공유하고 4는 별개다. 이미 한 집합인 0과 3을 다시 합쳐도 크기는 늘지 않아 sizeOf(3)은 4를 돌려준다. sizes 배열은 루트 인덱스에서만 최신 집합 크기를 유지하므로, sizeOf도 먼저 find로 루트를 찾아 조회한다.
비용과 실무 경계
원소 개 초기화에 시간과 공간이 든다. 역 아커만 함수 은 우주의 관측 가능한 원자 수를 훨씬 넘는 에서도 이하이므로 실무에서는 연산당 분할상환 상수 시간으로 동작한다.
운영상 주의할 경계는 간선 삭제(분리)를 직접 지원하지 않는다는 점이다. 한 번 합쳐진 집합을 다시 쪼개는 split 연산은 경로 압축이 원래 트리 구조를 평탄화해 버리기 때문에 에 되돌릴 수 없다. 간선 삭제나 되돌리기(rollback)가 필요한 오프라인 질의나 백트래킹에서는 경로 압축을 생략하고 크기 기준 병합()만 쓰면서 부모 배열 변경 이력을 스택에 기록해 복원해야 한다. 간선이 추가되기만 하는 점진적 연결성 검사나 크루스칼(Kruskal) 최소 신장 트리 알고리즘의 순환 판별에는 경로 압축을 포함한 유니온 파인드가 표준 해법으로 쓰인다.
같이 보기
각주
- Bernard A. Galler, Michael J. Fischer, “An Improved Equivalence Algorithm,” Communications of the ACM 7(5), 1964, pp.301–303, DOI. 계보와 가중 병합·경로 압축 분석은 Robert E. Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, ERL-M434, 1974-03-28, 서론 및 pp.2–4, 기관 보관 원문; JACM 22(2), 1975, pp.215–225, DOI. ↩
- Michael L. Fredman, Michael E. Saks, “The Cell Probe Complexity of Dynamic Data Structures,” Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp.345–354, DOI. ↩