[알고리즘] Disjoint-set (Union-Find)

서로소 집합 (disjoint-set)

• Disjoint-set(서로소 집합, Union-Find)은 여러 원소를 집합으로 묶고, 집합 간의 합치기와 대표 원소 찾기를 빠르게 처리하는 자료구조이다.
• 그래프에서 연결 여부, 사이클 판정, 최소 신장 트리(크루스칼) 등에 자주 사용이 되고있다.

기본 개념

• 집합: 여러 원소를 하나의 그룹으로 묶음
• Find: 원소가 속한 집합의 대표(루트) 찾기
• Union: 두 집합을 하나로 합치기

핵심 연산

• 초기화: 각 원소가 자기 자신을 대표로 가짐
• Find(x): x가 속한 집합의 대표를 반환
• Union(x, y): x와 y가 속한 집합을 합침

구현

class DisjointSet {
  constructor(n) {
    this.parent = Array(n).fill(0).map((_, i) => i);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 경로 압축
    }
    return this.parent[x];
  }
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      this.parent[rootY] = rootX;
    }
  }
}

def make_set(n):
    return [i for i in range(n)]

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x]) # 경로 압축
    return parent[x]

def union(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        parent[root_y] = root_x

사용예시

const ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(1, 2);
console.log(ds.find(2)); // 0
console.log(ds.parent); // [0,0,0,3,4]

parent = make_set(5)
union(parent, 0, 1)
union(parent, 1, 2)
print(find(parent, 2)) # 0
print(parent) # [0, 0, 0, 3, 4]

경로 압축과 랭크(최적화)

• 경로 압축: find 연산 시, 부모를 루트로 바로 연결해줌
• 랭크/크기 기준 합치기: 집합의 크기나 깊이에 따라 합침

class DisjointSet {
  constructor(n) {
    this.parent = Array(n).fill(0).map((_, i) => i);
    this.rank = Array(n).fill(1);
  }
  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] += 1;
    }
  }
}

def make_set(n):
    parent = [i for i in range(n)]
    rank = [1] * n
    return parent, rank

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x == root_y:
        return
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x
        rank[root_x] += 1

예시

const ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(3, 4);
console.log(ds.find(0) === ds.find(2)); // false
console.log(ds.find(3) === ds.find(4)); // true

parent = make_set(5)
union(parent, 0, 1)
union(parent, 3, 4)
print(find(parent, 0) == find(parent, 2)) # False
print(find(parent, 3) == find(parent, 4)) # True

요약

• Disjoint-set은 집합 관리에 특화된 자료구조이다.
• Find/Union 연산을 빠르게 처리
• 경로 압축, 랭크 최적화로 성능 향상
• 패턴이 유사하기 때문에 기억해 놓고 필요할때 바로 사용하도록 숙지해 놓도록 하자