이번 포스트에서는 집합 합치기찾기 또는 Disjoint Set 데이터 구조에 대해 알아보겠습니다. Disjoint Set은 여러 개의 집합을 효율적으로 관리하는 데 사용되며, 주로 그래프 알고리즘과 관련된 문제를 해결하는 데 활용됩니다.

Disjoint Set 개념

Disjoint Set은 서로소 집합이라고도 불리며, 각각의 집합에 대해 하나의 대표 원소를 지정하여 집합을 표현하는 방식입니다. 각 원소는 자기 자신을 대표로 지정하며, 두 집합을 합치거나 특정 원소가 속한 집합을 찾는 데 사용됩니다.

Disjoint Set 연산

Disjoint Set은 다음과 같은 연산을 지원합니다:

1. MakeSet(x): 새로운 원소 x를 단일 원소 집합으로 생성
2. Find(x): 원소 x가 속한 집합의 대표 원소를 반환
3. Union(x, y): 두 원소 x와 y가 속한 집합을 합침

Disjoint Set 구현

아래는 JavaScript로 Disjoint Set을 구현하는 예시입니다:

class DisjointSet {
  constructor(size) {
    this.parent = new Array(size);
    this.rank = new Array(size);
    for (let i = 0; i < size; i++) {
      this.parent[i] = i;
      this.rank[i] = 0;
    }
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX === rootY) {
      return;
    }
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
  }
}

위의 코드는 경로 압축과 트리 높이에 따른 합치기 최적화를 통해 Disjoint Set을 구현한 것입니다.

Disjoint Set 활용

Disjoint Set은 다양한 알고리즘 문제에서 활용됩니다. 예를 들어, 최소 비용 신장 트리(Minimum Spanning Tree) 알고리즘인 크루스칼 알고리즘과 그래프의 연결 여부를 확인하는 문제 등에 사용됩니다.

이상으로 Disjoint Set의 개념과 구현에 대해 알아보았습니다. Disjoint Set은 그래프 알고리즘 문제를 해결하는 데 있어서 매우 유용한 자료 구조 중 하나입니다.

참고 문헌

1. Sedgewick, R., Wayne, K. (2011). Algorithms. Addison-Wesley.
2. Dasgupta, S., Papadimitriou, C. H., Vazirani, U. V. (2008). Algorithms. McGraw-Hill Education.