알고리즘/개념

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

코딩하는상후니 2022. 8. 9. 23:02

 


 

 

*상호 배타적 집합 (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]

 

 

 


 

참고 링크

 

'알고리즘 > 개념' 카테고리의 다른 글

[Algo] @정렬 알고리즘 ( Sort Algorithm )  (0) 2022.08.19