고급 자료구조 - Disjoint Set

Disjoint? 뭘까요?

 

사전을 찾아보니까 "분리된" 이라는 형용사 입니다.

 

아하 그럼 disjoint set은 분리된 집합이라는 뜻이겠네요.

 

집합간의 intersection이 없는것이 disjoint set입니다!

 

disjoint set은 Kruskal MST algorithm과 같이 그래프 상에서 각각의 정점이 연결되었는지를 검사할때 요긴하게 사용됩니다. 

 

Minimum Spanning Tree는 Tree인 만큼 Cycle이 형성되면 안되는데요.

 

이 Cycle 찾기위해 인접한 정점을 일일이 찾는다면 상당히 복잡해집니다.

 

이럴때 사용하는 것이 Disjoint Set!

 

disjoint set을 활용하면 그래프 상에서 각각의 정점이 서로 붙어있는지(Cycle을 형성하는지) 알 수 있습니다.

 

먼저 자료구조니까 ADT부터 보겠습니다.

DISJOINT SET ADT

• makeset(a) - a를 원소로 갖는 별개의 집합을 만듭니다.
• find(a) - a원소가 속해있는 집합을 찾습니다.
• merge(a, b) - 개별로 된 두 집합을 합칩니다.
• equal(a, b) - a원소와 b원소가 같은 집합에 있는지 true false로 반환합니다.
• initial(n:size) - n개의 크기만큼 makeset을 이용해 Universe를 초기화합니다.

Universe는 가장 커다란 집합인데요. 코딩을 위해 배열로 구현합니다.

 

index와 Array value를 통해 disjoint set이라는 자료구조를 구현할 수 있습니다. 

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> U;
void makeset(int i);
int find(int i);
void merge(int p, int q);
bool equal(int p, int q);
void initial(int n);

int main() {
	int n;
	cout << "Universe size :";
	cin >> n;
	initial(n);
	int option, index, index2;
	while (true) {
		cout << "select ADT( 1: makeset, 2: find, 3: merge, 4: equal)" << endl;
		cin >> option;
		switch (option) {
		case 1:
			cout << "enter the index (0 <= index <= universe size" << endl;
			cin >> index;
			makeset(index);
			break;
		case 2:
			cout << "enter the index (0 <= index <= universe size" << endl;
			cin >> index; 
			cout <<"find : " << find(index) << endl;
			break;
		case 3:
			cout << "enter the two indices (0 <= index <= universe size" << endl;
			cin >> index >> index2;
			merge(index, index2);
			break;
		case 4:
			cout << "enter the two indices (0 <= index <= universe size" << endl;
			cin >> index >> index2;
			if (equal(index, index2)) {
				cout << "true" << endl;
			}
			else {
				cout << "false" << endl;
			}
			break;
		}
		cout << "index :";
		for (int i = 1; i <= n; i++) {
			cout << i << " ";
		}
		cout << endl << "array :";
		for (int i = 1; i <= n; i++) {
			cout << U[i] << " ";
		}
		cout << endl;
	}
}

void makeset(int i){
	U[i] = i;
}

int find(int i) {
	int j = i;
	while (U[j] != j) {
		j = U[j];
	}
	return j;
}

void merge(int p, int q) {
	p = find(p);
    q = find(q);
	if (p < q) {
		U[q] = p;
	}
	else {
		U[p] = q;
	}
}

bool equal(int p, int q) {
	if (U[p] == U[q]) {
		return true;
	}
	else {
		return false;
	}
}

void initial(int n) {
	U.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		makeset(i);
	}
}

 

실행화면

Universe의 사이즈를 초기화 하면서 1부터 10까지 개별적인 집합이 생성됩니다

 

{1} {2} {3} {4} {5} {6} {7} {8} {9} {10}

 

그리고 1과 3을 merge 했습니다.

 

{1,3} {2} {4} {5} {6} {7} {8} {9} {10}

 

또 1과 5를 merge 했습니다.

 

{1,3,5} {2} {4} {6} {7} {8} {9} {10}

 

다시 3과 8을 merge 했습니다.

 

{1,3,5,8} {2} {4} {6} {7} {8} {9} {10}

 

이렇게 볼 수 있습니다~

 

그리고 나서 5와 8이 equal인지 따져 물으면?

 

index 5와 index 8이 갖고있는 value가 각각 1과 3인데요.

 

3은 index 3의 value를 다시 확인해서 1 값을 가져옵니다.

 

index 5와 index 8이 같은 값을 가리키고 있으므로 같은 집합에 속해있다고 볼 수 있네요!

 

Disjoint set의 가장 기본적인 버전을 살펴보았습니다.

 

응용

https://strawberry-moon329.tistory.com/19?category=836932

백준 알고리즘 9938번 문제 : 방 청소

다음 버전은 다음 포스팅에서 이어서 하겠습니다~