서로소 집합(Disjoint Set)은 어떤 원소도 두 개 이상의 집합에 동시에 속할 수 없는, 서로 겹치지 않는 집합들의 모음입니다. 흔히 유니온-파인드(Union-Find)라고도 불리며, 부분집합에 대해 Union과 Find라는 두 가지 핵심 연산을 지원합니다.
주요 연산
Find(): 특정 원소가 어느 부분집합에 속해 있는지 찾는 연산으로, 해당 집합의 대표 원소(representative)를 반환합니다.
Union(): 서로 다른 두 부분집합을 하나의 집합으로 병합하는 연산입니다. 병합이 완료되면 한 집합의 대표 원소가 다른 집합의 대표 원소 역할을 하게 됩니다.
함수와 의사코드
시작
k를 원소라고 가정한다
makeset(k):
k.parent = k
Find(k):
만약 k.parent == k 이면
k를 반환한다
아니면
Find(k.parent)를 반환한다
Union(a, b):
두 집합 a와 b를 입력으로 받는다
aroot = Find(a)
broot = Find(b)
aroot.parent = broot
끝
C++ 구현 예제
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class DisjointSet { // 서로소 집합을 표현하는 클래스
unordered_map<int, int> parent;
public:
void makeSet(vector<int> const &wholeset){
// makeSet 연산 수행
for (int i : wholeset) // 각 원소마다 하나씩, 총 n개의 서로소 집합 생성
parent[i] = i;
}
int Find(int l) { // 원소 l이 속한 집합의 루트를 찾음
if (parent[l] == l) // l이 루트인 경우
return l;
return Find(parent[l]); // 루트를 찾을 때까지 부모를 재귀적으로 탐색
}
void Union(int m, int n) { // 두 부분집합 m과 n에 대해 Union 수행
int x = Find(m);
int y = Find(n);
parent[x] = y;
}
};
void print(vector<int> const &universe, DisjointSet &dis) {
for (int i : universe)
cout << dis.Find(i) << " ";
cout << '\n';
}
int main() {
vector<int> wholeset = { 6,7,1,2,3 }; // 전체 집합의 원소들
DisjointSet dis; // DisjointSet 클래스 초기화
dis.makeSet(wholeset); // wholeset의 각 원소에 대한 개별 집합 생성
dis.Union(7, 6); // 7과 6을 같은 집합으로 묶음
print(wholeset, dis);
if (dis.Find(7) == dis.Find(6)) // 두 원소가 같은 집합에 속하는지 확인
cout<<"Yes"<<endl;
else
cout<<"No";
if (dis.Find(3) == dis.Find(4))
cout<<"Yes"<<endl;
else
cout<<"No";
return 0;
}
실행 결과
6 6 1 2 3 Yes No
결과 해석
makeSet() 호출 직후에는 모든 원소가 자기 자신을 부모로 가지는 개별 집합을 형성합니다. 이후 Union(7, 6)을 실행하면 7과 6이 하나의 집합으로 병합되므로, Find(7)과 Find(6)은 동일한 대표 값인 6을 반환하게 됩니다. 따라서 첫 번째 비교에서는 "Yes"가 출력됩니다. 반면 원소 3과 4는 서로 다른 집합에 속해 있으므로 두 번째 비교에서는 "No"가 출력됩니다.
서로소 집합 자료구조는 그래프의 연결성 판단, 크루스칼(Kruskal) 알고리즘을 활용한 최소 신장 트리(MST) 구성, 네트워크 연결 상태 추적 등 다양한 분야에서 폭넓게 사용됩니다.