자료구조 - DisJointSet

DisJointSet은 집합을 나타낼 수 있는 간단한 자료구조이다. 집합은 어떠한 원소들이 하나의 공통 요소에 의해 묶여 있다는 것을 말한다. 위의 그림을 보면 p q r s는 X라는 요소에 묶여 있고 1 2 3 4 5 는 Y라는 요소에 묶여 있다. 즉 이를 구현하기 위해 생각해보면 각 원소들은 X나 Y라는 요소를 가리키고 있다고 생각하면 편하게 된다.

DisJointSet은 초기 모두 자기 자신을 부모로 가진다(각자 크기가 1인 자신만의 집합을 갖는다). 후에 Union연산을 하는 과정에서 병합되는 부모를 상대방의 부모로 가리키게 되면서 만약 같은 부모를 가리키고 있으면 같은 집합이다로 판단하게 된다.

DisJointSet은 Prim이나 Kruskal 알고리즘을 풀이 할 때 유용하다. 각각의 간선들을 이어나가면서 간선의 사이클이 발생시키지 않게 하기 위해서는 집합에 포함된 요소가 또다시 포함되지 않아야 하기 때문에 DisJointSet을 사용한다.

#include <cstdio>
#include <malloc.h>

using namespace std;

class DisJointSet
{
private:
	int size = 100;
	int* arr;
	void allocate()
	{
		arr = (int*) malloc( sizeof(int) * size );
		for (int i = 0; i < size; i++)
			arr[i] = i;
	} 
public:
	DisJointSet()
	{
		allocate();
	}
	DisJointSet(int s)
	{
		size = s;
		allocate();
	}

	int getParent(int x)
	{
		if (arr[x] == x)
			return x;
		else
			return x = getParent(arr[x]);
	}
	
	void unify(int x, int y)
	{
		int parentx = getParent(x);
		int parenty = getParent(y);

		if (parentx != parenty)
			arr[parentx] = parenty;
	}
};


void main()
{
	DisJointSet ds;

	ds.unify(2, 3);
	ds.unify(1, 3);

	printf("%d ", ds.getParent(2));
	printf("%d ", ds.getParent(1));
}