[UnionFind] Union Find의 Naive한 구현

작성일 | In

이번 글에서는 Union Find를 구현해봅시다. 배열을 이용한 구현과 트리를 이용한 구현, 총 두 가지를 살펴보도록 하겠습니다.

배열을 이용한 방법

가장 간단한 방법은 일차원 배열을 이용한 방법입니다.
group[i] = i번 원소가 속하는 집합의 번호 라고 정의합시다.

init

초기화 연산은 쉽게 구현할 수 있습니다.

1
2
3
void init(int n){
  for(int i=1; i<=n; i++) group[i] = i;
}

find

Find 연산은 특정 원소가 어떤 집합에 속하는지 알아내는 연산입니다.
O(1)만에 구할 수 있습니다.

1
2
3
int find(int v){
  return group[v];
}

union

Union 연산은 두 개의 집합을 한 집합으로 합치는 연산입니다.
원소 두 개가 주어지면, 두 원소가 속한 집합의 원소를 모두 같은 집합 번호로 바꿔주면 됩니다. union은 예약어이기 때문에 merge라는 이름을 쓰겠습니다.

1
2
3
4
5
6
7
8
bool merge(int u, int v, int n){
  u = find(u), v = find(v);
  if(u == v) return true;
  for(int i=1; i<=n; i++){
    if(group[i] == v) group[i] = u;
  }
  return false;
}

배열로 구현하면 Find연산은 O(1)이지만, Union연산은 O(n)입니다. Find 연산에 비해 Union 연산이 너무 느리기 때문에 다른 방법을 생각해봅시다.

트리를 이용한 방법

트리로 Union Find를 Naive하게 구현을 하면 최악의 경우 배열보다 느릴 수 있습니다. 그러나 두 가지 정도의 간단한 최적화만 해주면 아주 빨라집니다.

Naive한 방법을 알아봅시다.


트리를 이용해 구현을 하는 경우, 같은 집합에 속하는 원소끼리 하나의 트리로 묶어줍니다. 또한, 트리에는 루트가 존재하기 때문에 집합의 번호를 루트노드의 번호로 정합니다.

parent[i] = i번 노드의 부모 노드 라고 정의합시다.

init

init 연산은 배열로 구현한 것과 같이 간단하게 구현할 수 있습니다.

1
2
3
void init(int n){
  for(int i=1; i<=n; i++) parent[i] = i;
}

find

Find연산은 특정 노드에서 출발해 부모 노드로 하나씩 올라가면 마지막에 루트 노드를 만날 수 있습니다. 해당 루트 노드의 번호를 반환해줍시다. 재귀함수를 이용해 간단히 구현할 수 있습니다.

1
2
3
4
int find(int v){
  if(v == parent[v]) return v;
  return find(parent[v]);
}

union

Union연산은 두 원소가 다른 트리에 속해있다면, 즉 두 개의 트리의 루트가 다르다면 트리 하나를 다른 트리의 자손으로 넣어 두 트리를 합쳐줍니다.

1
2
3
4
5
6
bool merge(int u, int v){
  u = find(u), v = find(v);
  if(u == v) return true;
  parent[u] = v;
  return true;
}

Find연산의 수행시간은 트리의 깊이에 비례합니다. Union연산은 Find연산을 기반으로 작동하기 때문에 Union연산의 수행시간 또한 트리의 깊이에 비례합니다.

최악의 경우

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

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

다음 글

이전 글