Union Find, Disjoint Set

✔️ Union Find

◾️ Union Find는 Disjoint Set(상호 배타적 집합)을 표현할 때 쓰는 트리 자료 구조이다.

◾️ 상호 배타적 집합이란 공통 원소가 없는 배타적 집합을 뜻한다. 

◾️ Union 연산 : 두 원소 A, B가 주어질 때, 이들이 속한 두 집합을 하나로 합친다.

◾️ Find 연산 : 어떤 원소 A가 주어질 때 이 원소가 속한 집합을 반환한다. 

 

트리를 이용한 상호 배타적 집합의 표현

◾️ 두 원소가 같은 집합(트리)에 포함되어 있는지 확인하는 방법은 각 원소가 포함된 트리의 루트가 같은지 확인하는 것이다. 이렇게 하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야한다. 루트는 부모가 없으므로, 대개 자기 자신을 가리키도록 구현한다. 

 

두 집합의 표현

 

두 집합을 합친 결과

◾️ 두 트리를 합칠때 잘못하면 트리가 한쪽으로 기울어질 수 있다. 그렇게 되면 Union 연산과 Find 연산에서 각각 O(n) 시간이 걸리기 때문에 효율이 나빠지게 된다. 따라서 Union을 할 때 균형있는 트리를 만들어서 O(lgN) 시간을 만들어줘야 한다. 

 

👨‍💻 트리를 이용한 Disjoint Set 자료구조의 표현

#include<vector>
using namespace std;

struct NativeDisjointSet {

	vector<int> parent;

	//n개의 원소가 각각의 집합에 포함되어 있도록 초기화한다.
	NativeDisjointSet(int n) : parent(n) {
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	//u가 속한 트리의 루트 번호를 반환한다.
	int find(int u) const {
		if (u == parent[u]) return u;
		return find(parent[u]);
	}

	//u가 속한 트리와 v가 속한 트리를 합친다.
	//아래 코드에서는 항상 v트리 자식으로 u트리를 합친다.(사향 트리가 만들어질 가능성이 존재)
	void doUnion(int u, int v) {
		u = find(u); 
		v = find(v);
		if (u == v) return; //u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
		parent[u] = v;
	}

};

 

👨‍💻 최적화된 Disjoint Set의 구현 

#include<vector>
using namespace std;

struct OptimazedDisjointSet {

	vector<int> parent, rank;

	//n개의 원소가 각각의 집합에 포함되어 있도록 초기화한다. 
	OptimazedDisjointSet(int n) : parent(n), rank(n, 1) {
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	//find(u)를 통해 u가 속하는 트리의 루트를 찾아냈다. 이때 parnet[u]를 찾아낸 루트로 아예 바꿔 버리면,
	//다음번에 find(u)가 호출되었을 때는 경로를 따라 올라갈 것 없이 바로 루트를 찾을 수 있다.
	//즉, 부모노드를 루트노드로 바꿔버리는 것이다. 이를 '경로 압축 최적화'라고 한다.
	//재귀적인 구현 덕분에 u에서 루트까지 올라가는 경로상에 있는 모든 노드들에도 '경로 압축 최적화'가 자동으로 수행된다.
	int find(int u) {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}

	//두 개의 트리를 합칠 때, 항상 높이가 더 낮은 트리를 더 높은 트리 및에 집어 넣는다.
	//그럼으로서 트리의 높이가 높아지는 상황을 방지한다. (사향 트리 방지)
	void doUnion(int u, int v) {
		u = find(u);
		v = find(v);

		if (u == v) return; //u와 v가 이미 같은 집합에 속하는 경우를 걸러낸다.
		if (rank[u] > rank[v]) swap(u, v); //이제 rank[v]가 항상 rank[u] 이상이므로 u를 v의 자식으로 넣는다.
		parent[u] = v; 
		if (rank[u] == rank[v]) rank[v]++; //두 트리의 높이가 같을 경우에만 트리의 높이를 1 늘려준다.
	}

};