Algorithm - 합집합 찾기

📖 정의

서로소 집합들의 정보를 관리하면서 두 개의 원소가 같은 집합에 속해있는지 판별할 수 있는 알고리즘으로 노드들이 여러 그룹으로 나누어져 있을 때 같은 그룹의 노드들을 서로 연결하는 작업에 사용된다.

합집합 찾기는 보통 합집합 연산, 찾기 연산 두 가지 연산을 한다.

👩‍💻 구현

class UnionFind {
  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] = 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) {
      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]++;
    }
  }
}
  
const uf = new UnionFind(6);

uf.union(0, 1);
uf.union(2, 3);
uf.union(4, 5);

for (let i = 0; i < 6; i++) {
  console.log(`parent of node ${i}: ${uf.parent[i]}`);
}