disjoint-set (Union-Find)

disjoint set이란 상호 배타적인 부분 집합들로 나뉜 원소들에 대해 정보를 저장하고 조작하는 자료 구조이다. 

특히 Union - Find 자료구조라고 한다.

 

예를들어 각자 가장 좋아하는 색별로 팀을 나눈다고 생각해보자. 빨강을 좋아하는 팀, 파랑을 좋아하는 팀 등으로 나뉘지만 어느 누구도 두 개 이상의 팀에 속할 수 없다. 따라서 상호 배타적이라고 하는 것이다.

 

이를 구현하는 법은 같은 팀별로 같은 트리에 저장하는 것이다. 같은 팀인지를 판별하기 위해선 루트가 같은지만 확인하면 된다. 

이 때 쓰이는 두 함수가 Union과 FInd이다.

Union은 두 지점 u와 v를 합쳐주는 함수이다.

FInd는 어떤 노드 u의 루트 노드를 구해주는 함수이다.

아래 코드를 보면 이해가 될 것이다.

Union구현에 보통 parent 배열만 가지고도 구현할 수 있지만, 최악의 경우 루트에 자손이 한개씩 쭉 이어지는, 일종의 링크드 리스트처럼 이어지는 경우가 생길 수 있다. 이를 방지하기 위해 Rank 배열을 가지고 두 트리를 균등하게 합치는 것이다. 랭크가 낮은 트리를 랭크가 높은 트리에 합치면 합친 이후에도 높은 랭크가 최대 랭크값이 되므로 최적화가 가능하다.

 

---

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algorithm/disjoint-set(Union-Find).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> parent, setRank, setSize;

int find(int u) {
	if (parent[u] == u) return u;
	return parent[u] = find(parent[u]);
}

void Union(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	if (setRank[u] > setRank[v]) swap(u, v); //랭크가 낮은 노드를 높은 노드에 합친다.
	parent[u] = v;
	if (setRank[u] == setRank[v]) setRank[v]++; 
	setSize[v] += setSize[u];
}

int main()
{
	cin >> N;
	parent.resize(N);
	for (int i = 0; i < N; i++) parent[i] = i; 	//각자의 루트는 자기자신으로 초기화
	setRank.assign(N, 1); //각자 초기 랭크는 1이다.
	setSize.assign(N, 1); //초기 루트의 사이즈 역시 1
	
	Union(1, 2);
	Union(3, 4);
	cout << find(1) << " " << find(3);

}