[자료구조] 서로소 집합 자료구조 (Disjoint Set Union, DSU) - Union Find

이 글은 서로소 집합 자료구조(Disjoint Set Union, DSU)에 대해서 정리한 글입니다.

---

DSU와 Union Find
✅ "Union Find"라는 이름은 합치기를 뜻하는 Union과 찾기를 뜻하는 Find라는 두 가지의 주요 연산에서 유래한 표현으로 서로소 집합 자료구조(Disjoint Set Union, DSU)과 동일한 자료구조를 의미
✅ DSU는 "서로소(disjoint)인 여러 집합을 관리하고, 필요할 때 이 집합들을 합쳐(Union)주면서 집합의 대표나 구조를 빠르게 찾는(Find) 기법"을 의미하는 더 일반적이며 학술적인 표현 

Union Find랑 DSU는 동일한 자료구조를 나타내는 용어이며, 이 글에서 사용하는 Union Find와 DSU는 동일한 개념으로 이해하면 됩니다.

---

DSU(Disjoint Set Union)의 기본 개념

서로소(Disjoint) 집합

• 서로소 집합 또는 상호베타 집합은 서로 중복되는 원소가 없는 여러 개의 집합을 의미
  • ex. 집합 A와 집합 B에 대하여 $ A \cap B = \varnothing $ 이면, 집합 A와 B는 서로소 집합
• 대표자를 통해 각 집합을 구분
  • 대표자 (representative) : 집합에 속한 하나의 특정 멤버(원소)

DSU 자료구조

• 원소들이 각각 어떤 집합(그룹)에 속해 있는지를 관리
• Find와 Union이라는 주요 2가지 연산이 존재
  • find(x) : 원소 x가 어느 집합에 속해 있는지 대표(루트, root)를 찾아 반환
  • union(a, b) : 원소 a가 속한 집합과 원소 b가 속한 집합을 결합

활용 예시

• 그래프에서 사이클 판별
  • 무방향 그래프에서 두 노드를 연결할 때(간선 추가), 이미 두 노드가 같은 집합이라면 사이클이 형성된다는 것을 알 수 있음
• 최소 신장 트리(MST) - Kruskal 알고리즘
  • 간선을 가중치 오름차순으로 정렬 후, 간선을 하나씩 추가하며 Union-Find로 사이클 여부를 확인
• 동적 연결 요소 관리
  • 유저나 네트워크 노드가 "연결" 혹은 "친구" 상태가 되었는지 실시간으로 합치는 연산에 사용할 수 있음

DSU(Union Find)의 기본 동작 원리

대표 노드(루트, root)의 개념

• 각 집합은 트리(tree) 구조로 표현할 수 있으며, "대표 노드(루트)" 하나가 집합 전체를 대표
• 모든 원소는 자신이 속한 집합의 루트를 찾을 수 있음 (Find 연산)

초기화 (Initialization)

• 보통 n개의 원소(0 ~ n-1)가 있을 때, 처음에는 각각이 자기 자신만을 포함하는 집합으로 초기화함
  • parent[i] = i (자기 자신을 부모로 하는 트리 구조)

Union 연산

• 원소 a, b가 주어졌을 때, Find(a)와 Find(b)로 각자의 루트를 찾음
• 두 루트가 서로 다르면, 한쪽 루트를 다른 쪽 트리에 연결하여 두 집합을 결합

Find 연산

• 원소 x의 루트를 찾기 위해서는 parent[x]를 따라 거슬러 올라가 최종적으로 자기 자신의 부모로 갖는 노드(루트)를 만나면 그게 원소 x가 속한 집합의 대표
• 일반적으로 경로 압축(path compression)을 사용하여 Find 연산을 할 때 트리 높이를 줄여 다음 번에 더 빠른 탐색을 가능하게 함

Union Find 구현

/*
입력 예시
6개 노드 3개 간선 정보
6 3
1 2
4 5
2 5
*/

#include<iostream>
using namespace std;

// 대표 노드 체크를 위한 DAT
int parent[7]; // index : 노드 번호 / value : 대표 노드 번호

// Find : 특정 그룹의 대표 찾기 ( 재귀 )
int Find(int n) {
	//대표가 본인인 경우 return
	if (n == parent[n]) return n;
	//root 노드까지 찾아가기
	int root = Find( parent[n] );
	//대표 반환
	return root;
}

// Union : 그룹을 합친다.
void Union(int A, int B) {
	//그룹을 합칠 때, 같은 그룹인지 체크해야 한다.
	int rootA = Find(A);
	int rootB = Find(B);
	//같은 그룹이라면 종료
	if (rootA == rootB) return;
	//대표 정보 업데이트
	parent[rootB] = rootA;
}

int main() {
	// 초기 세팅 : 모두가 대표
	for (int i = 1; i <= 6; i++) {
		parent[i] = i;
	}

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int boss, employee;
		cin >> boss >> employee;
		Union(boss, employee);
	}

	return 0;
}

• parent 배열
  • 각 노드가 속한 집합의 대표 노드를 기록하고, union과 find 연산을 통해 갱신 
• Find(int n) 함수
  • n번 노드가 어떤 대표(루트)에 소속되어 있는지 재귀적으로 추적
  • 대표가 자기 자신인 노드를 찾으면 그 노드가 루트
• Union(int A, int B) 함수
  • A와 B의 루트를 비교해 다를 경우, 둘을 하나의 집합으로 결합
  • 위 코드는 간단한 구현으로, parent[rootB] = rootA;로 처리
• 초기 세팅 : 초기화
  • 모든 노드가 자기 자신만 포함하는 집합이 되도록 설정 (parent[i] = i)
  • 입력 간선을 받아 Union을 반복 호출해 집합을 통합

성능 개선 기법

경로 압축 (path compression)

• Find 연산을 수행하는 동안 만나는 모든 노드의 부모를 최종 루트로 직접 연결해주는 방식
• 트리의 높이가 극도로 낮아져 이후 Find 연산이 거의 $ O(1) $ 에 가깝게 수행

/*
입력 예시
6개 노드 3개 간선 정보
6 3
1 2
4 5
2 5
*/

#include<iostream>
using namespace std;

// 대표 노드 체크를 위한 DAT
int parent[7]; // index : 노드 번호 / value : 대표 노드 번호

// Find : 특정 그룹의 대표 찾기 ( 재귀 )
int Find(int n) {
	//대표가 본인인 경우 return
	if (n == parent[n]) return n;
	//root 노드까지 찾아가기 - 경로압축
    //해당 노드의 root 갱신
    parent[n] = Find( parent[n] );
	return parent[n];
}

// Union : 그룹을 합친다.
void Union(int A, int B) {
	//그룹을 합칠 때, 같은 그룹인지 체크해야 한다.
	int rootA = Find(A);
	int rootB = Find(B);
	//같은 그룹이라면 종료
	if (rootA == rootB) return;
	//대표 정보 업데이트
	parent[rootB] = rootA;
}

int main() {
	// 초기 세팅 : 모두가 대표
	for (int i = 1; i <= 6; i++) {
		parent[i] = i;
	}

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int boss, employee;
		cin >> boss >> employee;
		Union(boss, employee);
	}

	return 0;
}

union-by-rank (또는 union-by-size)

• 트리 높이나 노드 개수를 관리하여 항상 더 큰(또는 더 깊은) 트리에 작은 트리를 합치는 방식을 적용하면 트리의 높이를 최소화하여 Find를 더 빠르게 만들 수 있음

대표 연습 문제

✔️ BOJ 1717번: 집합의 표현

✔️ BOJ 1976번: 여행 가자

✔️ BOJ 4195번: 친구 네트워크

✔️ BOJ 16562번: 친구비

---

핵심 요약

• DSU 혹은 Union Find는 여러 집합을 효율적으로 합치고, 특정 원소가 속한 집합의 대표(루트)를 빠르게 찾는 자료구조
• Find(x)와 Union(a, b)가 핵심 연산으로, Find(x)는 원소 x가 어느 집합에 속해 있는지 루트를 찾는 역할을 수행하며, Union(a, b)는 원소 a의 집합과 원소 b의 집합을 합치는 역할을 수행
• 경로 압축(path compression)과 union-by-rank, union-by-size 방식을 사용하여 최적화 가능