유니온 파인드
개요
유니온 파인드(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)을 함께 썼을 때의 비용은 여러 연구를 거쳐 좁혀졌다. Hopcroft와 Ullman은 1973년 상한을 제시했고, Tarjan은 1975년 최대 비용을 으로 분석했다. 이때 실행열은 개 단독 집합에서 시작하며, 번의 FIND와 번의 UNION이 섞여 있다. 은 FIND 횟수다. Fredman과 Saks는 1989년 셀당 비트인 온라인 셀 프로브 모델에서, 그러한 어려운 실행열에 총 셀 접근이 필요하다는 하한을 보였다.23
크기 기준 병합과 경로 압축
각 원소 는 부모 를 가리키고, 집합의 대표인 루트만 로 자기 자신을 가리킨다. find(x)는 부모 포인터를 따라 루트를 찾는다. 두 원소의 루트가 같으면 같은 집합이다. 다만 루트 번호는 트리 균형에 따라 병합 시 바뀔 수 있는 내부 식별자이므로, 집합에 고정된 업무상 이름이나 속성이 필요하다면 루트를 키로 삼아 별도 테이블에 보관해야 한다.
아무 기준 없이 한 루트를 다른 루트 밑에 붙이면 트리가 한 줄로 길어져 탐색이 까지 퇴화한다. union(a, b)에서 원소 수가 적은 트리의 루트를 큰 트리의 루트 밑에 붙이면(크기 기준 병합), 어떤 노드의 깊이가 늘어날 때마다 그 노드가 속한 집합의 크기가 최소 두 배로 커지므로 경로 압축 없이도 트리의 최대 높이가 이하로 묶인다. 여기에 find(x)가 루트까지 올라가며 거친 모든 노드의 부모를 루트로 곧바로 바꿔치기하는 경로 압축을 더하면, 개 원소의 초기화와 그 뒤 번의 union/find 연산에 대한 총비용 상한은 다음과 같다. 은 표준적인 한 변수 역 아커만 함수다.
실행 예제
C++20
C++20판은 원소 번호를 size_t로 저장한다. 메서드에 넘기는 번호는 생성한 count개의 원소 범위 안에 있어야 한다. union은 C++ 예약어이므로 병합 메서드 이름을 unite로 쓰고, 크기가 같으면 TypeScript판처럼 첫 인자의 루트를 유지한다.
#include <cstddef>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class UnionFind {
std::vector<std::size_t> parent;
std::vector<std::size_t> sizes;
public:
explicit UnionFind(std::size_t count) : parent(count), sizes(count, 1) {
std::iota(parent.begin(), parent.end(), std::size_t{0});
}
std::size_t find(std::size_t value) {
auto root = value;
while (root != parent[root]) root = parent[root];
while (value != root) {
const auto next = parent[value];
// 검색한 경로의 노드들을 루트 바로 아래에 연결한다.
parent[value] = root;
value = next;
}
return root;
}
bool unite(std::size_t a, std::size_t b) {
auto rootA = find(a);
auto rootB = find(b);
if (rootA == rootB) return false;
if (sizes[rootA] < sizes[rootB]) std::swap(rootA, rootB);
parent[rootB] = rootA;
sizes[rootA] += sizes[rootB];
return true;
}
std::size_t sizeOf(std::size_t value) {
return sizes[find(value)];
}
};
int main() {
UnionFind groups(5);
groups.unite(0, 1);
groups.unite(2, 3);
groups.unite(1, 2);
std::cout << std::boolalpha;
std::cout << (groups.find(0) == groups.find(3)) << '\n';
std::cout << (groups.find(0) == groups.find(4)) << '\n';
std::cout << groups.unite(0, 3) << '\n';
std::cout << groups.sizeOf(3) << '\n';
return 0;
}true
false
false
4TypeScript
원소 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을 처리하려면 원래 간선과 대체 경로 정보가 필요한데, 기본 구조는 이를 보관하지 않는다. 그래서 압축을 하지 않은 트리만으로도 간선 삭제 뒤의 연결성을 일반적으로 알아낼 수 없다. 최근 병합을 되돌리는 오프라인 질의나 백트래킹에서는 보통 경로 압축을 생략하고 크기 병합만 사용한다. 그러면 find는 최악 이고, 병합이 바꾼 부모와 크기의 이전 값을 이력 스택에서 복원하면 된다. 경로 압축까지 쓰는 롤백은 압축 중의 부모 변경도 모두 기록하고 그 비용을 따로 분석한다. 간선이 추가되기만 하는 연결성 검사와 크루스칼 최소 신장 트리의 순환 판별에는 크기 병합과 경로 압축을 함께 쓰는 방식이 알맞다.
같이 보기
각주
- 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. ↩
- John E. Hopcroft, Jeffrey D. Ullman, “Set Merging Algorithms,” SIAM Journal on Computing 2(4), 1973, pp.294–303. DOI. Tarjan 1975 defines t(m,n) as maximum sequence time; Fredman–Saks 1989, Theorem 5, states the CPROBE(log n) lower bound. ↩