여러 대의 컴퓨터가 복잡한 랜선으로 얽혀 있는 거대한 네트워크 망을 관리한다고 상상해 보십시오. 무작위로 두 대의 컴퓨터를 골랐을 때, "이 두 컴퓨터가 서로 통신이 가능한 상태인가(같은 네트워크에 속해 있는가)?"를 실시간으로 빠르게 판별해야만 합니다. 만약 매번 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)을 돌려서 경로를 찾는다면, 네트워크 규모가 커질수록 시스템은 심각한 과부하에 걸리게 될 것입니다. 이렇게 여러 개의 노드가 존재할 때, 어떤 노드들이 서로 같은 집합(Set)에 묶여 있는지를 가장 빠르고 효율적으로 관리하고 판별해 주는 마법의 자료구조가 있습니다. 바로 '유니온-파인드(Union-Find)', 학술적 용어로는 '서로소 집합(Disjoint Set)'입니다. 크루스칼(Kruskal) 알고리즘의 심장이기도 한 이 자료구조의 원리와, 속도를 O(1)에 가깝게 만들어주는 두 가지 궁극의 최적화 기법을 완벽하게 해부해 보겠습니다.
1. 서로소 집합(Disjoint Set)과 유니온 파인드의 개념
서로소 집합이란 수학적으로 '공통 원소가 전혀 없는 두 개 이상의 집합'을 의미합니다. 쉽게 말해, 1번부터 10번까지의 학생이 있을 때 {1, 2, 3}이 한 팀이고 {4, 5}가 한 팀이라면, 이 두 팀은 서로 겹치는 멤버가 없으므로 서로소 집합 관계에 있는 것입니다. 유니온 파인드는 이 집합들을 컴퓨터 메모리 상에서 '트리(Tree)' 형태로 구성하여 부모-자식 관계로 엮어서 관리하는 알고리즘입니다.
1-1. 두 가지 핵심 연산: Union과 Find
이름에서 알 수 있듯이, 이 자료구조는 단 두 가지의 아주 명확한 기능을 제공합니다.
- Find (찾기): 특정 노드가 주어졌을 때, 그 노드가 속한 집합의 대장(Root 노드)이 누구인지 찾아내는 연산입니다. 대장이 같으면 같은 집합(팀)에 속한 것이고, 대장이 다르면 다른 집합에 속한 것입니다.
- Union (합치기): 서로 다른 두 개의 집합을 하나의 거대한 집합으로 병합하는 연산입니다. 한 집합의 대장을 다른 집합의 대장 밑으로 들어가게(자식 노드로) 연결해 버리면 간단하게 두 집합이 통일됩니다.
2. 배열을 이용한 기초적인 구현과 치명적 한계
유니온 파인드는 놀랍게도 복잡한 객체 생성 없이, 1차원 배열인 `parent[]` 하나만으로 완벽하게 구현할 수 있습니다. 초기에는 모든 노드가 자기 자신을 대장(부모)으로 가리키도록 `parent[i] = i`로 세팅합니다.
2-1. Find와 Union의 기본 로직
// 부모 노드를 찾는 Find 함수 (재귀)
int find(int x) {
if (parent[x] == x) return x; // 내가 대장(루트)이면 내 번호 반환
return find(parent[x]); // 아니면 내 부모의 부모를 계속 찾아 올라감
}
// 두 집합을 합치는 Union 함수
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) parent[rootB] = rootA; // B의 대장을 A의 대장 밑으로 편입
}
위 코드는 매우 직관적이지만, 치명적인 문제점을 안고 있습니다. 만약 1번 밑에 2번, 2번 밑에 3번... 이런 식으로 한쪽으로만 길게 늘어진 편향 트리(일자형 트리)가 만들어진다면 어떨까요? 마지막 노드의 대장을 찾기 위해 최악의 경우 O(N)의 시간이 걸려, 비싼 DFS를 쓰는 것과 다를 바가 없어집니다.
3. 극강의 속도를 위한 2가지 최적화 마법
이 O(N)의 탐색 시간을 O(1)에 가까운 아커만 함수 역함수 수준(상수 시간)으로 줄이기 위해, 선배 개발자들은 두 가지 천재적인 최적화 기법을 도입했습니다.
3-1. 경로 압축 (Path Compression) - Find 최적화
Find 연산을 수행하며 대장(루트)을 찾아 거슬러 올라갈 때, 거쳐 가는 모든 노드들의 부모를 아예 최종 대장(루트 노드)으로 다이렉트로 꽂아버리는(업데이트하는) 기법입니다. 코드를 단 한 줄만 수정하면 됩니다: `return parent[x] = find(parent[x]);` 이렇게 하면, 한 번 탐색했던 노드들은 다음번 탐색 시 단계를 거칠 필요 없이 한 번에 대장을 가리키게 되어 트리의 높이가 극단적으로 납작해집니다.
3-2. 랭크에 의한 병합 (Union by Rank) - Union 최적화
두 집합을 합칠(Union) 때, 아무렇게나 합치는 것이 아니라 항상 높이(Rank)가 낮은 트리를 높이가 높은 트리의 밑(자식)으로 들어가게 만드는 기법입니다. 이렇게 하면 키가 큰 트리의 전체 높이가 불필요하게 더 높아지는 것을 완벽하게 방지할 수 있습니다. 두 트리의 높이가 우연히 같을 때만, 합친 트리의 높이를 +1 증가시켜 주면 됩니다.
1. 유니온 파인드(Union-Find)는 여러 노드가 서로 같은 그룹(서로소 집합)에 속해 있는지를 빠르고 효율적으로 판별하고 병합하는 트리 기반 자료구조입니다.
2. 집합의 대표를 찾는 Find 연산과 두 집합을 합치는 Union 연산이 핵심으로, 크루스칼 알고리즘에서 사이클을 판별하는 데 필수적으로 쓰입니다.
3. 일자형 트리가 되는 최악의 성능 저하를 막기 위해, 경로 압축(Path Compression)과 랭크 병합(Union by Rank) 기법을 반드시 적용하여 O(1)에 가까운 성능을 확보해야 합니다.