[UnionFind] Union Find의 최적화

작성일 | In

최악의 경우

이전 글 마지막 부분을 다시 가져와봅시다.

트리를 이용해 구현을 하는 경우 아래 그림과 같이 치우친 형태의 트리가 나올 수 있습니다.

이렇게 되면 Union, Find 두 개의 연산 모두 O(n)이 되버립니다. 이를 해결하기 위한 최적화 방법은 다음 글에서 다루도록 하겠습니다.

Union by Rank

이 문제는 두 트리를 합칠 때 높이가 더 낮은 트리를 높은 트리 밑에 넣어준다면 어느정도 해결할 수 있습니다. 이런 최적화를 union by rank라고 합니다. rank[i] = i번 노드를 루트로 하는 서브트리의 대략적인 높이 라고 정의합시다.
par[i] = i번 노드의 부모 노드 라고 정의합시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void init(int n){
  for(int i=1; i<=n; i++) par[i] = i, rank[i] = 1;
}

int find(int v){
  if(v == par[v]) return v;
  return find(par[v]);
}

bool merge(int u, int v){
  u = find(u), v = find(v);
  if(u == v) return true;
  if(rank[u] > rank[v]) swap(u, v);
  par[u] = v;
  if(rank[u] == rank[v]) rank[v]++;
}

Path Compression

한 가지 최적화를 더 해주면 아주 빨라지게 됩니다.

이런 식으로 Find 연산을 수행할 때 거쳐가는 모든 노드를 루트 노드 바로 밑에 붙여주면, 다음에 Find 연산을 수행할 때 연산량이 많이 줄어들게 됩니다.
이 방법을 경로 압축(path compression) 이라고 합니다.
최종적으로 나온 Union Find의 코드는 아래와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void init(int n){
  for(int i=1; i<=n; i++) par[i] = i, rank[i] = 1;
}

int find(int v){
  if(v == par[v]) return v;
  return par[v] = find(par[v]);
}

bool merge(int u, int v){
  u = find(u), v = find(v);
  if(u == v) return true;
  if(rank[u] > rank[v]) swap(u, v);
  par[u] = v;
  if(rank[u] == rank[v]) rank[v]++;
}

이전 글