알고리즘 문제를 풀다 보면, 여러 원소가 '같은 집합에 속해 있는지'를 빠르게 확인하고, 또 '두 집합을 하나로 합쳐야' 하는 상황을 종종 마주친다. 처음에는 단순 배열이나 그래프 탐색으로 접근했지만, 데이터의 크기가 커질수록 비효율의 벽에 부딪히는 경험을 했다. 이 문제를 효과적으로 해결하기 위해 고안된 자료구조가 바로 서로소 집합(Disjoint Set)이며, 이를 구현하는 알고리즘이 Union-Find이다. 이번 글에서는 이 개념을 차근차근 정리해보고자 한다.
Disjoint Set 이란?
Disjoint Set(서로소 집합)은 말 그대로 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조다. '서로소' 또는 '상호 배타적(mutually exclusive)'이라는 말처럼, 각 집합은 공통 원소를 가지지 않는다. 예를 들어 {1, 2}, {3, 4}, {5} 와 같은 집합들의 모음을 생각할 수 있다.
이 자료구조를 효과적으로 다루기 위해 사용하는 알고리즘이 바로 Union-Find이다.
Union-Find 알고리즘과 세 가지 연산
Union-Find는 Disjoint Set을 표현하기 위한 알고리즘으로, 이름에서 알 수 있듯 Union과 Find 연산이 핵심이다. 여기에 초기화를 위한 make-set 연산을 더해 총 세 가지 연산으로 구성된다.
make-set(x): 초기화 연산. x라는 원소 하나만을 포함하는 새로운 집합을 만든다.make-set union(x, y): 합집합 연산. x가 속한 집합과 y가 속한 집합을 하나로 합친다.union find(x): 찾기 연산. x가 어떤 집합에 속해 있는지 확인하기 위해, 해당 집합의 대표값(representative)을 반환한다. 보통 트리의 루트 노드가 이 역할을 한다.find
구현 방법: 배열 vs 트리
Union-Find를 구현하는 데는 여러 방법이 있지만, 가장 효율적인 것은 트리 구조를 이용하는 것이다. 왜 그럴까? 단순 배열과 비교해보면 그 이유를 알 수 있다.
배열로 구현할 경우
find(x):Array[x]값을 바로 읽으면 되므로 O(1)로 매우 빠르다.union(x, y): y가 속한 집합의 모든 원소를 찾아 x의 집합 번호로 바꿔야 하므로, 전체 배열을 순회해야 하는 최악의 경우 O(N)이 소요된다.
트리로 구현할 경우
각 집합을 하나의 트리로 표현하며, 루트 노드가 그 집합의 대표값이 된다.
find(x): x 노드에서 시작해 루트 노드에 도달할 때까지 부모 노드를 따라 올라간다. 시간 복잡도는 트리의 높이에 비례한다.union(x, y): x와 y의 루트 노드를 찾은 뒤, 한쪽 루트가 다른 쪽 루트의 자식이 되도록 연결한다. 이 연산 역시 두 번의find가 핵심이므로 시간 복잡도는 트리의 높이에 의해 결정된다.
union 연산의 비효율을 개선하기 위해 트리 구조를 채택했지만, 여기서 새로운 문제가 발생한다.
Union-Find 최적화: 더 빠르게, 더 효율적으로
만약 트리 구조가 한쪽으로만 치우쳐진 편향 트리(skewed tree)가 되면 어떻게 될까? 원소 N개에 대해 높이가 N-1인, 연결 리스트와 같은 형태가 될 수 있다. 이 경우 find 연산의 시간 복잡도는 최악의 경우 O(N)이 되어 배열 구현의 장점을 모두 잃게 된다.
 |
| seems to be linked-list rather than tree |
이 문제를 해결하고 거의 O(1)에 가까운 시간 복잡도를 얻기 위해 두 가지 핵심적인 최적화 기법이 사용된다.
1. 경로 압축 (Path Compression)
경로 압축은 find 연산을 수행하면서 만나는 모든 노드가 직접 루트 노드를 가리키도록 경로를 수정하는 기법이다. find(x)를 호출하면 x에서 루트까지 거쳐 가는 모든 노드들의 부모가 최종적으로 루트 노드로 갱신된다.
이 기법을 적용하면 트리의 높이가 급격히 낮아져, 이후의 find 연산이 매우 빨라진다.
/* find(x) with Path Compression */
int find(int x) {
// 베이스 케이스: 자신이 루트 노드인 경우
if (root[x] == x) {
return x;
} else {
// 재귀적으로 부모의 루트를 찾고,
// 자신의 부모를 루트로 직접 연결하여 경로를 압축한다.
return root[x] = find(root[x]);
}
}
 |
| path compression |
2. Union-by-Rank (or Union-by-Height)
Union-by-Rank는 union 연산을 최적화하는 기법이다. 두 트리를 합칠 때, 아무 규칙 없이 합치면 편향 트리가 생기기 쉽다. 이를 방지하기 위해 항상 높이(rank)가 더 낮은 트리를 높이가 더 높은 트리의 루트에 붙이는 방식을 사용한다.
두 트리의 높이가 다르면, 낮은 트리를 높은 트리에 붙인다. (전체 높이 변화 없음)
두 트리의 높이가 같다면, 한쪽을 다른 쪽에 붙이고 루트가 된 트리의 높이를 1 증가시킨다.
이 방법을 사용하면 트리가 급격히 높아지는 것을 방지하여 전체적으로 균형 잡힌 형태를 유지할 수 있다.
 |
| compare w/, w/o union by rank |
아래는 경로 압축과 Union-by-Rank를 모두 적용한 C++ 코드이다.
class UnionFind
{
private:
vector<int> parent, rank;
public:
UnionFind(int n)
{
parent.resize(n + 1);
rank.resize(n + 1, 1); // 모든 노드의 초기 rank는 1
for (int i = 1; i <= n; i++)
{
parent[i] = i; // 자기 자신을 부모로 초기화
}
}
// 경로 압축이 적용된 find 연산
int find(int x)
{
if (parent[x] != x)
{
parent[x] = find(parent[x]);
}
return parent[x];
}
// Union-by-Rank가 적용된 union 연산
void unionSets(int a, int b)
{
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB)
{
// rank가 더 높은 트리에 낮은 트리를 붙인다.
if (rank[rootA] > rank[rootB])
{
parent[rootB] = rootA;
}
else if (rank[rootA] < rank[rootB])
{
parent[rootA] = rootB;
}
else // rank가 같다면
{
parent[rootB] = rootA; // 한쪽에 붙이고
rank[rootA]++; // rank를 1 증가시킨다.
}
}
}
};
결론
Disjoint Set이라는 자료구조와 이를 구현하는 Union-Find 알고리즘은 단순한 아이디어에서 출발한다. 하지만 경로 압축과 Union-by-Rank라는 두 가지 강력한 최적화 기법을 통해, 시간 복잡도를 거의 상수 시간에 가깝게(O(alpha(N))) 만들 수 있다. 여기서 $\alpha(N)$은 아커만 함수의 역함수로, 실제 모든 N 값에 대해 4보다 작은 값을 가지므로 사실상 상수 시간으로 봐도 무방하다.
그래프에서 사이클을 판별하거나(Kruskal 알고리즘 등), 네트워크 연결 상태를 확인하는 등 다양한 문제에 활용되는 핵심 자료구조인 만큼, 그 원리를 제대로 이해하고 넘어가는 것이 중요하겠다는 생각이 들었다. 다음번에는 Union-Find를 활용한 실제 알고리즘 문제를 풀어보며 개념을 다져봐야겠다.
