[Algo]@Disjoint Set ( 상호 배타적 집합 )

 

---

 

 

*상호 배타적 집합 (Disjoint Set)

 

 

 

=> 유니온-파인드 Union-Find (합치기-찾기)

 

=> 서로 다른 원소들이 같은 집합에 속해있는지, 속해있지 않은지 판별 가능.

 

=> 대표적으로 크루스칼 알고리즘 MST 를 찾는데 활용. ( 싸이클 방지 )

 

 

 

int Find(int u)
{
	if (u == _parent[u])
		return u;

	return Find(_parent[u]);
}



void Union(int u, int v) 
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	_parent[u] = v;
}

 

 

 

 

*문제점

 

 

1. Find 함수는

Union 연산 시, 덧붙여지는 각 원소들이 새로운 parent 를 가리키도록 갱신해야하기 때문에

O(n) 시간 복잡도를 가짐.

 

 

ex)

Union(A, B) -> Union(B, C) -> Union(C, D) ....

B, C, D, ... 모두 parent = A 로 갱신해주어야함.

 

 

 

 

 

2. Union 함수는 높이가 낮은 트리에 높이가 높은 트리가 추가되면 비효율적.

 

ex)

Union(A, B) -> Union(C, D) -> Union(E, F) ....

Find 연산 시, 트리의 깊이만큼 재귀함수 호출.

 

 

 

 

 

 

* 해결방안

 

 

1. 경로 압축 ( path compression )

 

 

=> 직접적으로 부모노드를 가리키도록 갱신

 

int Find(int u)
{
	if (u == _parent[u])
		return u;

	return _parent[u] = Find(_parent[u]);
}

 

 

 

 

 

 

2. Union-By-RANK

 

=> 트리의 깊이를 Rank 로 나타낸다.

 

void Union(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v) return;

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

	_parent[u] = v;

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

 

=> Rank (Depth) 를 사용하는 이유.

깊이가 적은 트리를 깊이가 더 깊은 트리 아래로 추가하기 위해서

 

 

 

 

*왜 RANK 가 같을 때 +1 을 해주는 것일까 ??

 

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

 

같은 RANK 의 트리를 합칠 때, 비로소 해당 트리의 높이가 +1 증가되어짐.

 

ex)

{ 3, 5, 7 }  ( Union ) { 1, 2, 6 }

 

       [3]

   [5]     [7]   +   [1]

                     [2]    [6]

 

 

 

---

 

참고 링크

 

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0