Union-Find의 최적화 과정

Union-Find는 말 그대로 임의의 그룹과 그룹을 묶고(Union) 두 노드가 같은 그룹인지 확인(Find) 하는 알고리즘이다. 하나씩 따라 해 보면서 어떻게 구현하고, 최적화시키는지 확인해보자.

 

Union Find는 그룹을 하나의 트리로 표현한다. 이렇게 하면 두 노드가 같은 그룹인지 확인할 때 단순히 root 노드가 같은지만 확인하면 되기 때문에 간단해진다.

void unionGroup(int x, int y) {
  int rootX = findRoot(x);
  int rootY = findRoot(y);
  parent[rootX] = rootY;
}

bool isSameGroup(int x, int y) {
  return findRoot(x) == findRoot(y);
}

 

첫 번째 함수는 x와 y를 묶는 작업, 두 번째 함수는 x와 y가 같은 그룹인지 확인하는 함수다.

두 함수에서 공통으로 사용하는 함수가 있는데, 트리의 root를 찾아주는 findRoot(x)이다. 이것만 잘 구현한다면 자료구조가 간결하게 완성된다.

 

그러면 문제점도 파악할 겸 예제를 돌려보자.
node는 node번호 이름이고, parent는 해당 node를 포함하는 그룹(트리)에서 자신의 부모를 의미한다.

 

예제

1. 초기 상태

아무도 연결되지 않은 상태

node	1	2	3	4	5	6
parent	1	2	3	4	5	6

 

2. Union <1, 2>, <5, 6> 

 

1을 2와, 5를 6과 연결

 

node	1	2	3	4	5	6
parent	2	2	3	4	6	6

3. Union <1,5>

2(1의 루트)를 6(5의 루트)과 연결

node	1	2	3	4	5	6
parent	2	6	3	4	6	6

 

---

 

이와 같이 트리구조를 유지하며 각 그룹과 그룹을 관리한다. 매 Union마다 빠르게 그래프로 적용시킬 수 있어 보이지만 최악의 경우에는 아래와 같은 구조도 발생할 수 있다.

루트찾는데 $O(n)$..!

 

이런 트리가 만들어진다면 findRoot(x)의 시간 복잡도가 $O(n)$이 되어버릴 수 있다. 따라서 Union 하는 과정에서 트리의 높이를 계속 낮춰주는 작업을 해야 한다.

 

두 가지 방법을 적용하면 매우 효율적으로 구현할 수 있다.

 

개선

1. 그룹과 그룹을 합칠 때 작은 그룹의 root를 큰 그룹의 root에게 합친다

Union과정에서 어느 한 그룹의 트리 높이는 한 칸 증가할 수밖에 없다.
그렇기 때문에 합치는 과정에서 더 작은 그룹(또는 트리의 높이)을 희생시키는 방향으로 더 좋은 트리를 유지할 수 있다.

void unionGroup(int x, int y) {
  int rootX = findRoot(x);
  int rootY = findRoot(y);

  if(size[rootX] < size[rootY]){
    parent[rootX] = rootY;
    size[rootY] += size[rootX];
  }
  else {
    parent[rootY] = rootX;
    size[rootX] += size[rootY];
  }
}

 

2. root를 찾는 반복되는 과정을 줄인다

임의의 노드 x에 대해서 findRoot(x)를 이미 한 기록이 있다면 두 번째부터는 반복할 필요가 없다.
부모가 누군지는 관심 없고 root가 누군지만 관심 있기 때문에 매번 parent를 root로 바꿔준다면 트리의 높이가 아주 낮게 유지될 것이다.

int findRoot(int x) {
  if(parent[x] == x) return x;
  return parent[x] = findRoot(x);
}

 

이런 개선 과정을 통해 아래와 비슷하게 그래프를 유지하며 빠르게 조작할 수 있다.

 

정리

트리의 높이를 줄이는 테크닉을 사용하지 않는다면 Union 연산마다 $O(n)$의 시간이 소요된다. 하지만 union과 find 방법을 개선시키면 $O(α(N))$으로 만들 수 있다. union find의 시간 복잡도

여기서 나오는 $α(N)$는 아커만 함수로 $α(2^{2^{2^{2^{16}}}})$ < 5를 만족시킬 만큼 매우 작은 함수이다. 두 가지 개선을 항상 유지하는 Union-Find라면 사실상 $O(1)$이라 생각하고 사용하면 된다.