6-1. 상호 배타적 집합 (Disjoint Set)

최소 스패닝 트리를 공부하기 전에, 최소 스패닝 트리에 적용되는 서로소 집합에 대해서 공부한다.

 

1. 상호 배타적 집합(서로소 집합) ; Disjoint Set
- 공통 원소(혹은 공통 부분 집합)를 가지지 않는 집합, 교집합이 없는 집합들.

ex) { 1, 2, 3 } 과 { 4, 5, 6 } 은 서로소 집합이다.

 

(1) 유니온-파인드(Union-Find) 알고리즘

- 유니온 (Union) : 두 개의 서로소 집합을 하나로 합침.

- 파인드 (Find) : 주어진 원소를 가지는 집합을 찾음. 주어진 원소의 루트 노드를 찾는 것이 목표.

 

2. 트리 구조를 이용한 표현

class NaiveDisjointSet
{
public:
	NaiveDisjointSet(int n) : _parent(n)
	{
		for (int i = 0; i < n; i++)
			_parent[i] = i; // 자기의 부모는 자신
	}

	int Find(int u) // 루트 노드를 찾기
	{
		if (u == _parent[u]) // 찾는 u가 루트 노드임
			return u;

		return Find(_parent[u]); // 재귀적 호출로 위로 타고 올라가기
	}

	void Merge(int u, int v) // 합치기, u가 v 밑으로 들어감
	{
		u = Find(u); // u의 루트 노드 찾기
		v = Find(v); // v의 루트 노드 찾기

		if (u == v) // 예외 처리
			return;

		_parent[u] = v;
	}

private:
	vector<int> _parent;
};

단, 트리가 불균형하기 떄문에 이 코드는 그렇게 빨리 작동하지 않는다.

 

 

3. 랭크 최적화(균형 최적화) ; Rank Union(Balanced Union)

원소 개수가 적은 집합을 원소 개수가 많은 집합에 넣는 방식.

class NaiveDisjointSet
{
public:
	NaiveDisjointSet(int n) : _parent(n), _rank(n, 1)
    //~~~~~

//~~~~~
private:
	vector<int> _parent;
	vector<int> _rank;
};

클래스의 생성자에 _rank 맴버 변수를 받도록 설정한다.

	void Merge(int u, int v) // 합치기, u가 v 밑으로 들어감
	{
		u = Find(u);
		v = Find(v);

		if (u == v) // 예외 처리
			return;

		if (_rank[u] > _rank[v])
			swap(u, v);

		// 항상 rank[u] <= rank[v] 이다

		_parent[u] = v;
		if (_rank[u] == _rank[v])
			_rank[v]++;
	}

트리의 높이가 같은 서로소 집합이 하나로 합쳐지면, 높이가 1 늘어난다(루트 노드의 아래로 들어가기 때문).

	int Find(int u) // 루트 노드를 찾기
	{
		if (u == _parent[u]) // 찾는 u가 루트 노드임
			return u;

		return _parent[u] = Find(_parent[u]); // 재귀적 호출로 위로 타고 올라가기
	}

Find 함수의 재귀적 호출 부분을 수정하면 찾는 속도를 최적화 할 수 있다.