Union-Find(Disjoint Set)는 어떤 문제에 사용하나요?

Union-Find(Disjoint Set)는 여러 원소가 어떤 집합에 속하는지 빠르게 관리하고, 두 집합을 합치는 자료구조입니다. 연결 요소 판별, 사이클 검출, 크루스칼 MST 알고리즘에서 자주 사용됩니다.

핵심 개념

• find(x)는 x가 속한 집합의 대표(root)를 찾습니다.
• union(a, b)는 두 원소가 속한 집합을 합칩니다.
• 경로 압축(path compression)과 union by rank/size를 쓰면 거의 상수 시간에 가깝게 동작합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = Array(n).fill(1);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[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];
    return true;
  }
}

실무에서 주의할 점

• Union-Find는 집합을 합치기에는 좋지만, 이미 합쳐진 집합을 다시 분리하는 연산에는 적합하지 않습니다.
• 동적 그래프에서 간선 삭제까지 처리해야 하면 다른 자료구조가 필요합니다.
• 대표 원소가 어떤 값인지는 구현 최적화에 따라 달라질 수 있으므로 비즈니스 의미를 부여하면 안 됩니다.

실무 적용 가이드

• '같은 그룹인가?'를 많이 묻고 그룹 병합이 있는 문제에서 먼저 떠올립니다.
• 무방향 그래프에서 간선을 추가하며 사이클 여부를 검사할 때 유용합니다.
• Kruskal 알고리즘에서는 가중치가 작은 간선부터 보며 서로 다른 집합이면 union합니다.

함께 연결해서 보면 좋은 키워드

Union-Find, Disjoint Set, Path Compression, Kruskal

정리

Union-Find(Disjoint Set)는 여러 원소가 어떤 집합에 속하는지 빠르게 관리하고, 두 집합을 합치는 자료구조입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.