Union-Find 알고리즘을 이해하고 구현할 수 있다.

Goal

  • Disjoint Set과 Union-Find의 개념을 이해할 수 있다.
  • Union-Find 알고리즘을 구현할 수 있다.

Disjoint Set의 개념

Disjoint Set이란

서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

Union-Find의 개념

Union-Find란

Disjoint Set을 표현할 때 사용하는 알고리즘

Union-Find의 연산

참고 Union-Find 알고리즘을 트리 구조로 구현하는 이유

  1. 배열
    • Array[i]: i번 원소가 속하는 집합의 번호(즉, 루트 노드의 번호)
    • make-set(x)
      • Array[i] = i와 같이 각자 다른 집합 번호로 초기화한다.
    • union(x, y)
      • 배열의 모든 원소를 순회하면서 y의 집합 번호를 x의 집합 번호로 변경한다.
      • 시간 복잡도: O(N)
    • find(x)
      • 한 번만에 x가 속한 집합 번호를 찾는다.
      • 시간 복잡도: O(1)
  2. 트리
    • 같은 집합 = 하나의 트리, 즉 집합 번호 = 루트 노드
    • make-set(x)
      • 각 노드는 모두 루트 노드이므로 N개의 루트 노드 생성 및 자기 자신으로 초기화한다.
    • union(x, y)
      • x, y의 루트 노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합한다.
      • 시간 복잡도: O(N)보다 작으므로 find 연산이 전체 수행 시간이 지배한다.
    • find(x)
      • 노드의 집합 번호는 루트 노드이므로, 루트 노드를 확인하여 같은 집합인지 확인한다.
      • 시간 복잡도: 트리의 높이와 시간 복잡도가 동일하다. (최악: O(N-1))

Union-Find의 과정과 사용 예시

Union-Find의 과정

Union-Find의 사용 예시

전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할(아래 참고*)하는 데 자주 사용된다.

참고 분할(Partition)이란

Union-Find의 기본적인 구현 방법

/* 초기화 */
int root[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
    parent[i] = i;

/* find(x): 재귀 이용 */
int find(int x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
    if (root[x] == x) {
        return x;
    } else {
        // 각 노드의 부모 노드를 찾아 올라간다.
        return find(root[x]);
    }
}

/* union(x, y) */
void union(int x, int y){
    // 각 원소가 속한 트리의 루트 노드를 찾는다.
    x = find(x);
    y = find(y);

    root[y] = x;
}

Union-Find의 최적화한 구현 방법

최악의 상황

find 연산 최적화

/* 초기화 */
int root[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
  root[i] = i;
}

/* find(x): 재귀 이용 */
int find(int x) {
  if (root[x] == x) {
      return x;
  } else {
      // "경로 압축(Path Compression)"
      // find 하면서 만난 모든 값의 부모 노드를 root로 만든다.
      return root[x] = find(root[x]);
  }
}

union 연산 최적화

/* 초기화 */
int root[MAX_SIZE];
int rank[MAX_SIZE]; // 트리의 높이를 저장할 배열
for (int i = 0; i < MAX_SIZE; i++) {
  root[i] = i;
  rank[i] = 0; // 트리의 높이 초기화
}

/* find(x): 재귀 이용 */
int find(int x) { // 동일
}

/* union1(x, y): union-by-rank 최적화 */
void union(int x, int y){
   x = find(x);
   y = find(y);

   // 두 값의 root가 같으면(이미 같은 트리) 합치지 않는다.
   if(x == y)
     return;

   // "union-by-rank 최적화"
   // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다. 즉, 높이가 더 높은 쪽을 root로 삼음
   if(rank[x] < rank[y]) {
     root[x] = y; // x의 root를 y로 변경
   } else {
     root[y] = x; // y의 root를 x로 변경

     if(rank[x] == rank[y])
       rank[x]++; // 만약 높이가 같다면 합친 후 (x의 높이 + 1)
   }
}
/* union2(x, y): 두 원소가 속한 트리의 전체 노드의 수 구하기 */
int nodeCount[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
   nodeCount[i] = 1;

int union2(int x, int y){
   x = find(x);
   y = find(y);

   // 두 값의 root가 같지 않으면
   if(x != y) {
       root[y] = x; // y의 root를 x로 변경
       nodeCount[x] += nodeCount[y]; // x의 node 수에 y의 node 수를 더한다.
       nodeCount[y] = 1; // x에 붙은 y의 node 수는 1로 초기화
   }
   return nodeCount[x]; // 가장 root의 node 수 반환
}

관련된 Post

References