Disjoint Set
서로소 집합, 분리 집합 이란 서로 공통된 원소를 가지고 있지 않은 두개 이상의 집합을 말한다.
트리로 구성하는 이유
트리에 속해있는 루트 노드를 그 집합을 대표하는 노드로 두고 한 원소가 어떤 집합에 속해있는지 확인하는 과정을 해당 원소가 자신이 속한 루트 노드가 누구인지 확인하는 과정을 통해 판별하기 때문이다. 같은 트리의 루트 노드는 한개, 즉 자식 노드들은 하나의 루트노드를 가질 수 밖에 없다. 부모노드를 타고 올라가다 보면 루트 노드를 만나고 자신이 어느 집합에 속해있는지 알 수 있다.
실제 그래프를 사용하지 않고 배열에 자신의 부모만 저장해 놓으면 같은 집합에 속해있는지, 속해있지 않은지 알 수 있다.
Union & Find
- Union(합연산)
- Find(부모, 루트노드 찾기)
서로 다른 두개의 서로소 집합을 합치기 위해 Union 연산을 수행한다. 서로소 집합 사이에 공통되는 원소는 없기 때문에 하나의 집합으로 합치기 위해서는 위와 같이 표현한 두 집합 중 하나를 다른 한 쪽 트리에 합치는 것으로 구현한다.
한쪽 트리의 루트 노드의 부모를 바꾸는 순간 루트노드의 딸린 자식 노드들의 다른 집합과 연결되는 것을 확인할 수 있다.
트리를 합치는 경우 서로소 집합을 구현할 때, 시간 효율성을 고려해야하는 경우가 발생한다. 바로 서로소 집합에서 부모를 찾꼬 루트 누도가 무엇인지 찾는 과정이다.
원소가 어느 집합에 속해있는지 찾고 해당 원소를 다른 집합과 합치는 과정이 바로 union&find이다.
하지만, 최악의 경우 트리가 한쪽으로 연결되어있을 경우,
O(트리의 높이, 크기) 만큼의 시간이 걸릴 수 있다. 이런 최악의 경우를 대비하기 위해 2가지 메커니즘이 존재한다.
1. Path Compression (경로 압축)
경로 압축은 집합 내 한 원소의 루트를 찾는 과정을 포함시켜 압축시키는 방법이다. 특정 원소에서 부모를 향해 가면서 원소와 루트 사이의 모든 원소들을 방문한다.
union(int parent[], int a, int b){
a = find(parent, a) // 부모 찾기
b = find(parent, b)
for (int i = 0;i < parent.size();i++){
if (parent[i] == b)
parent[i] = a;
}
}
or
find(int parent[], int a)
{
if (a == parent[a]) return a;
return parent[a] = find(parent[a]);
}a 쪽 집합으로 부모를 다 일치시킨다. 이런 방법을 사용한다면 이후 find 연산 시 집합을 확인할 때 O(1)의 시간 복잡도를 갖게된다.
2. Rank Compression (랭크 압축)
랭크 압축은 합하는 과정을 향상시키므로 이후 한 원소에서 루트를 찾아가는 경로 자체를 줄일 수 있다. 한 트리의 루트를 다른 트리의 루트의 자식으로만 합하여 불필요한 경로를 단축시킨다.
1. 트리의 깊이가 더 작은 쪽을 큰 쪽에 합
2. 트리의 크기가 더 작은 쪽을 큰쪽에 합
int rank[n+1] = {1};
void union(int a, int b){
a = find(a);
b = find(b);
if (rank[a] < rank[b]) swap(a, b);
rank[a] += rank[b];
parent[b] = a;
find 과정의 시간 복잡도 O(logn)
