그래프O(α(n))

유니온 파인드 — 그룹·사이클 판정

"같은 그룹이야?"를 거의 O(1)에 답해요. 사이클 판정·최소 신장 트리의 뼈대예요.

이럴 때 써요

두 원소가 같은 그룹(연결)인지 빠르게 묻고 답할 때
간선을 하나씩 이으며 연결 요소 개수를 셀 때
그래프에 사이클이 생기는지 판정할 때
크루스칼로 최소 신장 트리(MST)를 만들 때

개념

각 원소는 자기 그룹의 대표(root)를 가리켜요. parent[x]에 부모를 적어 두고, 부모를 따라 계속 올라가면 결국 대표에 닿아요. 두 원소가 같은 대표를 가지면 같은 그룹이에요. 그래서 연산은 딱 두 개예요 — find(대표 찾기)와 union(두 그룹 합치기).그냥 두면 트리가 일자로 길어져 find가 느려져요. 두 가지로 눌러요. 경로 압축: find 하는 김에 지나온 노드를 대표에 바로 붙여요. 사이즈(랭크) 기준 합치기: 작은 트리를 큰 트리 밑에 붙여 높이를 낮게 유지해요. 둘을 합치면 한 연산이 거의 상수, O(α(n))이 돼요.

"union 몇 번 + 사이클 감지" — parent가 바뀌는 과정
원소 0..4, 처음엔 각자 자기 자신이 대표
parent = [0, 1, 2, 3, 4]   (size 전부 1)
union(0,1): 루트 0,1 다름 → 1을 0 밑에   parent=[0, 0, 2, 3, 4]
union(2,3): 루트 2,3 다름 → 3을 2 밑에   parent=[0, 0, 2, 2, 4]
union(1,2): find(1)=0, find(2)=2 다름 → 2를 0 밑에
           parent=[0, 0, 0, 2, 4]   (0 그룹: {0,1,2,3})
union(0,3): find(0)=0, find(3)=0  같은 루트!
           → 이미 연결됨, 여기서 이으면 **사이클**

연결 요소 개수는 서로 다른 대표의 수예요. 아니면 처음 개수 n에서 시작해, union이 실제로 두 그룹을 합칠 때마다 하나씩 줄이면 바로 알 수 있어요. 크루스칼 MST도 이걸 그대로 써요 — 간선을 가벼운 순으로 보며, 두 끝이 다른 그룹일 때만 골라 잇고, 같은 그룹이면(=사이클) 버려요.

패턴 코드

유니온 파인드 (경로 압축 + 사이즈 기준)find는 대표를 찾으며 지나온 노드를 대표에 바로 붙여요. union은 작은 트리를 큰 트리 밑에 넣고, 실제로 합쳤을 때만 true를 돌려줘 사이클 판정에 써요.

javascript
Copy code
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n; // 연결 요소 개수
  }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // 경로 압축
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false; // 이미 같은 그룹 = 사이클
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra; // 작은 트리를 큰 트리 밑에
    this.size[ra] += this.size[rb];
    this.count--;
    return true; // 실제로 합침
  }
  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

이 유형으로 풀어보기

← 다익스트라 최단경로 1차원 DP — 점화식 세우기 →