카카오톡 친구 추천에서 "A와 B가 친구이고, B와 C가 친구이면 A와 C도 알 수도 있는 사람"으로 묶이는 원리를 아시나요?
이처럼 여러 개의 점(노드)들이 서로 같은 네트워크(집합)에 속해 있는지 빠르게 확인하고 합칠 때 사용하는 마법 같은 알고리즘이 바로 유니온 파인드(서로소 집합, Disjoint Set)입니다. 오직 1차원 배열 하나만으로 복잡한 그래프의 연결 상태를 O(1)에 가깝게 파악할 수 있는 극강의 효율을 자랑합니다.
1. Union(합치기)과 Find(대장 찾기)
2. 핵심 치트키: 경로 압축 (Path Compression)
만약 데이터가 1-2-3-4-5 처럼 기차놀이 하듯 한 줄로만 길게 연결된다면 대장을 찾는데(Find) 시간이 오래 걸릴 것입니다.
이를 방지하기 위해 Find를 수행하면서 거쳐간 모든 꼬봉 노드들이 직접 최상위 대장을 가리키도록 배열 값을 업데이트합니다. 이것이 바로 유니온 파인드 속도의 핵심인 경로 압축(Path Compression)입니다.
// 자바스크립트 기준 경로 압축 코드
find(x) {
if (parent[x] === x) return x;
// 재귀적으로 대장을 찾으면서 내 부모값을 대장으로 덮어씀
return parent[x] = find(parent[x]);
}
💡 실무 지식: 도대체 언제 쓰나요?
- 최소 신장 트리 (MST): 네트워크 케이블 깔기, 최단 경로 길찾기 등 크루스칼(Kruskal) 알고리즘에서 사이클이 생기는지 방지할 때 무조건 쓰입니다.
- 네트워크 및 소셜 연결 분석: "이 유저와 저 유저가 몇 다리 건너면 아는 사이인가?"를 판별하는 클러스터링 알고리즘에서 맹활약합니다.
// 📂 UnionFind.js (JavaScript)
// 1차원 배열(parent) 하나로 모든 집합 관계를 완벽하게 표현합니다.
class UnionFind {
constructor(size) {
// 처음에는 자기 자신을 부모로 가리킵니다. (각자 독립된 집합)
this.parent = Array.from({ length: size }, (_, i) => i);
}
// 🌟 Find: 자신이 속한 집합의 대장(Root)을 찾습니다.
find(x) {
if (this.parent[x] === x) {
return x; // 자신이 대장이면 그대로 반환
}
// 💡 경로 압축(Path Compression)
// 대장을 찾는 길에 만나는 모든 노드들이 직접 대장을 가리키게 만듭니다. (속도 극대화)
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
// 🌟 Union: 두 집합을 하나로 합칩니다.
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
if (rootA !== rootB) {
this.parent[rootB] = rootA; // B의 대장을 A의 대장 밑으로 편입시킵니다.
}
}
// 두 노드가 같은 집합에 있는지 확인
isConnected(a, b) {
return this.find(a) === this.find(b);
}
}
// 🌐 테스트 실행
const uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
console.log("1과 3은 같은 네트워크인가요?", uf.isConnected(1, 3)); // true (1-2-3 연결됨)
console.log("1과 5는 같은 네트워크인가요?", uf.isConnected(1, 5)); // false
