JavaScript Union-Find: 경로 압축과 크기 합치기로 연결 상태 관리하기

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

서로 떨어진 장치 5개를 케이블로 연결한다고 생각해 보겠습니다. 케이블 하나가 추가될 때마다 “0번과 3번이 같은 네트워크인가?”를 묻는다면, 매번 BFS로 모든 간선을 읽는 비용이 쌓입니다. Union-Find는 실제 이동 경로 대신 연결 성분만 기억합니다. 답에 필요한 정보가 “같은 묶음인가”까지일 때 원래 그래프를 저장하지 않아도 됩니다.

원소는 0부터 n−1까지의 정수입니다. find(x)는 대표 번호, same(a,b)는 연결 여부, sizeOf(x)는 성분 크기를 반환합니다. union(a,b)는 서로 다른 성분을 합쳤을 때만 true를 반환하고 count를 1 줄입니다. 대표 번호는 최소 번호라는 의미가 없습니다. 같은 크기이면 첫 인수의 대표를 남기는 것은 이 구현의 규칙일 뿐, 호출 순서를 바꾸면 대표는 달라질 수 있습니다.

n은 0~1,000,000으로 제한합니다. 이 제한은 이론적 한계가 아니라 교육용 배열의 과도한 할당을 막는 계약입니다. n=0인 구조는 만들 수 있지만 원소가 없으므로 find(0)는 오류입니다. 공개 메서드 외에 parent와 sizes를 직접 고치면 뒤에서 증명할 불변식이 깨집니다.

정확성을 지키는 불변식

parent가 만드는 구조는 여러 개의 뿌리 있는 나무입니다. 루트만 parent[root]===root이고, 나머지는 같은 성분 안의 조상을 가리킵니다. 루트에서만 sizes[root]가 정확한 성분 크기입니다. 합쳐진 옛 루트의 sizes는 남아 있어도 더 이상 의미가 없으므로 sizeOf는 반드시 find를 먼저 호출합니다.

크기 합치기는 작은 나무의 루트를 큰 나무의 루트 아래에 붙입니다. 어떤 원소의 깊이가 1 증가했다면 그 원소가 속한 성분의 크기는 적어도 2배가 됩니다. 크기는 n을 넘지 않으므로 깊이는 O(log n)입니다. 합치기를 원소 a,b에 직접 적용하지 않고 대표 ra,rb에 적용해야 성분 일부만 떼어 붙이는 실수를 피할 수 있습니다.

경로 압축은 첫 반복에서 찾은 루트로 방문한 모든 부모를 바꿉니다. 이 변경은 대표 자체를 바꾸지 않아 연결 관계를 보존합니다. next를 먼저 저장하지 않으면 원래 경로를 잃고 첫 원소만 압축하게 됩니다. 같은 성분이면 union이 즉시 끝나므로 중복 케이블과 자기 자신으로의 연결은 count를 줄이지 않습니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 union-find.cjs로 저장하고 파일이 있는 폴더에서 node union-find.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

class UnionFind {
  constructor(n) {
    if (!Number.isInteger(n) || n < 0 || n > 1_000_000) {
      throw new RangeError('n은 0~1,000,000 정수여야 합니다.');
    }
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.sizes = Array(n).fill(1);
    this.count = n;
  }
  check(x) {
    if (!Number.isInteger(x) || x < 0 || x >= this.parent.length) {
      throw new RangeError('원소 번호가 범위를 벗어났습니다.');
    }
  }
  find(x) {
    this.check(x);
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    while (this.parent[x] !== x) {
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }
  union(a, b) {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.sizes[ra] < this.sizes[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.sizes[ra] += this.sizes[rb];
    this.count--;
    return true;
  }
  same(a, b) { return this.find(a) === this.find(b); }
  sizeOf(x) { return this.sizes[this.find(x)]; }
}

module.exports = { UnionFind };

if (require.main === module) {
  const d = new UnionFind(5);
  for (const [a, b] of [[0, 1], [2, 3], [1, 2], [0, 3]]) d.union(a, b);
  console.log(JSON.stringify({ groups: d.count, size: d.sizeOf(3), same: d.same(0, 4) }));
}

직접 실행 출력:

{"groups":2,"size":4,"same":false}

constructor는 초기화 O(n)을 한 번 지불합니다. find의 두 while은 “대표 찾기”와 “경로 다시 쓰기”의 책임을 분리합니다. 재귀를 쓰지 않으므로 JavaScript 호출 스택에 의존하지 않습니다.

union에서 크기 비교 뒤 ra,rb를 교환하는 이유는 뒤의 세 줄을 항상 같은 방향으로 실행하기 위해서입니다. parent[rb]=ra, sizes[ra]+=sizes[rb], count–는 하나의 합병에 해당합니다. 이 세 변경을 같은 성분 처리에도 실행하면 크기가 중복 집계됩니다.

실행 예제는 네 개의 연결 요청을 처리합니다. 마지막 요청은 이미 연결된 두 원소이므로 그룹 수는 2에 머뭅니다. 출력의 size는 원소 3이 속한 네 원소 성분을 뜻하고, 4는 여전히 혼자이므로 same은 false입니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

α(n)은 역 아커만 함수입니다. 실제 크기에서 매우 작더라도 “무조건 최악 O(1)”로 적으면 틀립니다. 상환 시간은 긴 연산열의 총비용을 나눠 본 값이며, 입력을 무작위로 가정하는 평균 시간과 다릅니다.

간선을 삭제하거나 특정 원소를 집합에서 분리하는 연산에는 이 구조를 그대로 쓰면 안 됩니다. 이미 압축한 부모에는 어떤 간선 때문에 연결됐는지 정보가 없습니다. 삭제가 섞인 문제는 오프라인 역처리, rollback DSU 또는 동적 연결성 구조가 필요한지 따로 설계해야 합니다.

실제 경로, 최단 거리, 간선 목록이 필요하면 그래프 인접 리스트와 BFS/DFS가 적합합니다. 연결이 한 번만 주어지고 질의도 한 번이라면 단순 순회가 더 읽기 쉽습니다. Union-Find의 장점은 연결 추가와 반복 질의가 함께 있을 때 드러납니다.

연습으로 확인하기

새 연결마다 전체 묶음 수와 한쪽 묶음 크기를 함께 기록해 보세요. 단순 true/false보다 “언제 상태를 바꿔야 하는가”를 더 엄격하게 확인할 수 있습니다.

[창작 문제] 이동 실험실의 연결 일지

AtCoder A – Disjoint Set Union — 간선 추가와 연결 여부 질의를 연습하는 공식 문제입니다. 원문은 링크에서 확인하며, 아래 창작 문제와 출력 계약은 다릅니다.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• AtCoder Library 공식 DSU 문서
• AtCoder A – Disjoint Set Union