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