코딩테스트 JS Union-Find: 연결 성분 수와 크기 구하기

Node.js 24 CommonJS용 전체 풀이입니다. union-find-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 .input.json | node .union-find-problem.cjs

macOS / Linux:
node union-find-problem.cjs < input.json

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)]; }
}

function solve({ n, links }) {
  const d = new UnionFind(n);
  return links.map(([a, b]) => {
    d.union(a, b);
    return [d.count, d.sizeOf(a)];
  });
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

links.map의 각 순회가 일지 한 줄에 대응합니다. union이 false여도 sizeOf(a)는 계산해야 합니다. 처음 두 요청으로 크기 2인 성분 두 개가 생기고 세 번째 요청으로 크기 4가 됩니다. 네 번째는 같은 성분 안의 중복 요청이므로 [2,4], 다섯 번째는 혼자 남은 장치 4의 자기 연결이므로 [2,1]입니다.

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

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

초기화 O(n), q개 요청의 총 시간 O(n+qα(n)) 상환, 구조 O(n)와 반환 일지 O(q) 공간입니다. 개별 요청의 최악은 O(log n)입니다.

표본과 경계를 직접 확인하려면 다음 코드를 union-find-check.cjs로 저장하고 같은 폴더에서 node union-find-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./union-find-problem.cjs');

assert.deepEqual(
  solve({
  "n": 5,
  "links": [
    [
      0,
      1
    ],
    [
      2,
      3
    ],
    [
      1,
      2
    ],
    [
      0,
      3
    ],
    [
      4,
      4
    ]
  ]
}),
  [[4,2],[3,2],[2,4],[2,4],[2,1]],
);
assert.deepEqual(
  solve({
  "n": 0,
  "links": []
}),
  [],
);