어떤 파티에 n명의 사람들이 왔다고 합시다. 레크레이션 강사가 이 중 생일이 같은 사람들끼리 팀을 구성하라고 소리치자, 사람들은 얼른 움직이기 시작합니다. 처음에는 누가 자신과 생일이 같은지 모르기 때문에 모두 혼자 돌아다니지만, 생일이 같은 사람을 한 번 찾으면 이 둘은 팀을 이뤄 같이 움직입니다. 그리고 다른 팀과 생일이 같다는 것을 확인하면 곧장 두 팀은 합쳐지지요.
이 상황을 어떻게 자료 구조로 표현할 수 있을까요? 파티에 온 사람들의 전체 집합을 두고 보면, 팀은 이 집합을 여러 개의 부분 집합들로 쪼갠 것입니다. 각 팀은 생일이 같은 사람들로 구성되어 있기 때문에, 두 개 이상의 팀에 속한 사람은 없다는 점에 유의합시다. 이렇게 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 가 바로 유니온-파인드 자료 구조 입니다.
이 상황을 표현하기 위해서 우선 각 사람을 0부터 n-1까지의 원소로 표현하기로 한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만듭니다. 두 사람 a와 b가 서로 생일이 같다는 사실을 알 때마다 두 사람이 포함된 집합을 합치게 되지요. 이와 같은 일들을 구현하기 위해 다음과 같은 세 가지 연산이 필요합니다.
-
초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화합니다.
-
합치기(union) 연산 : 두 원소 a, b가 주어질 때 이들이 속한 두 집합을 하나로 합칩니다.
-
찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환합니다.
이 때 합치기(union), 찾기(find)의 두 연산을 지원한다고 해서 이 자료 구조를 유니온-파인드(union-find) 자료 구조라고 부릅니다.
배열로 상호 배타적 집합 표현하기
상호 배타적 집합들을 표현하는 가장 간단한 방법은 1차원 배열 하나를 이용하는 것입니다. 다음과 같은 배열 belongsTo를 만듭시다.
belongsTo[i] = i번 원소가 속하는 집합의 번호
처음에 belongsTo를 각자 다른 숫자(belongsTo[i] = i로 두면 되겠죠)로 초기화하면 크기가 1인 n개의 집합을 쉽게 만들 수 있습니다. 이렇게 하면 찾기 연산을 상수 시간에 구현할 수 있습니다.
트리를 이용한 상호 배타적 집합의 표현
두 원소가 같은 트리에 속해 있는지 확인하는 가장 직관적인 방법은 각 원소가 포함된 트리의 루트를 찾은 뒤 이들이 같은지 비교 하는 것입니다. 트리와 루트는 항상 1:1 대응되기 때문에, 루트가 같다면 두 노드가 같은 트리에 속해 있음은 자명합니다. 따라서 트리의 루트에 있는 원소를 각 집합의 대표 라고 부릅시다. 따라서 트리에서 찾기 연산은 주어진 원소가 포함된 트리의 루트를 찾는 것 으로 구현됩니다.
이런 찾기 연산을 구현하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 합니다. 반면 부모에서 자식으로 내려갈 일은 없기 때문에 부모는 자식에 대한 포인터를 가지고 있을 필요가 없지요. 이와 같이 트리를 이용한 집합 표현에서는 두 원소가 포함된 집합을 합치기도 아주 간단합니다. 각 트리의 루트를 찾은 뒤, 하나를 다른 한쪽의 자손으로 넣으면 되지요.
// 트리를 이용해 상호 배타적 집합을 구현
struct DisjointSet {
vector<int> parent;
DisjointSet(int n) : parent(n) {
for (int i = 0; i < n; ++i)
parent[i] = i;
}
// u가 속한 트리의 루트의 번호를 반환한다.
int find(int u) const {
if (u == parent[u]) return u;
return find(parent[u]);
}
// u가 속한 트리와 v가 속한 트리를 합친다.
void merge(int u, int v) {
u = find(u);
v = find(v);
// u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
if (u == v) return;
parent[u] = v;
}
};