JavaScript 그래프 연습: 연결 구역 크기를 작은 순서로 출력하기

한 파일로 실행하는 전체 정답

'use strict';

class Graph {
  constructor(directed = false) {
    this.directed = directed;
    this.adj = new Map();
  }

  addVertex(vertex) {
    if (typeof vertex !== 'string') throw new TypeError('vertex must be a string');
    if (!this.adj.has(vertex)) this.adj.set(vertex, []);
    return this;
  }

  addEdge(from, to) {
    this.addVertex(from);
    this.addVertex(to);
    this.adj.get(from).push(to);
    if (!this.directed) this.adj.get(to).push(from);
    return this;
  }

  hasEdge(from, to) {
    return this.adj.get(from)?.includes(to) ?? false;
  }

  toMatrix() {
    const vertices = [...this.adj.keys()];
    const indices = new Map(vertices.map((vertex, index) => [vertex, index]));
    const matrix = Array.from({ length: vertices.length },
      () => new Array(vertices.length).fill(0));
    for (const [from, neighbors] of this.adj) {
      for (const to of neighbors) matrix[indices.get(from)][indices.get(to)] = 1;
    }
    return { vertices, matrix };
  }

  bfs(start) {
    if (!this.adj.has(start)) return [];
    const visited = new Set([start]);
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
      const vertex = queue[head];
      head += 1;
      for (const next of this.adj.get(vertex)) {
        if (visited.has(next)) continue;
        visited.add(next);
        queue.push(next);
      }
    }
    return queue;
  }
}

function solve({ vertices, edges }) {
  const graph = new Graph();
  for (const vertex of vertices) graph.addVertex(vertex);
  if (graph.adj.size !== vertices.length) throw new TypeError('duplicate vertex');
  for (const [from, to] of edges) {
    if (!graph.adj.has(from) || !graph.adj.has(to)) {
      throw new TypeError('edge endpoint is not in vertices');
    }
    graph.addEdge(from, to);
  }
  const visited = new Set();
  const sizes = [];
  for (const start of vertices) {
    if (visited.has(start)) continue;
    const queue = [start];
    visited.add(start);
    let head = 0;
    while (head < queue.length) {
      const vertex = queue[head];
      head += 1;
      for (const next of graph.adj.get(vertex)) {
        if (visited.has(next)) continue;
        visited.add(next);
        queue.push(next);
      }
    }
    sizes.push(queue.length);
  }
  return sizes.sort((a, b) => a - b);
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: 한 BFS가 한 연결 요소를 셉니다

addVertex를 먼저 호출해야 간선에 나오지 않은 정점도 adj에 남습니다. addEdge는 원래 없는 정점을 자동 생성할 수 있는 API지만 이 문제에서는 명시적 목록이 전체 세계이므로 끝점을 확인한 뒤 호출합니다. 자료구조의 편의 기능과 문제의 입력 계약을 구분합니다.

바깥 반복은 정점 목록 전체를 읽습니다. 이미 visited에 있으면 이전 BFS에서 같은 구역으로 센 것이므로 건너뜁니다. 새 정점이면 새 큐에 넣고 이웃을 따라가면서 처음 발견한 정점만 넣습니다. 무방향 그래프에서 이 탐색은 시작점과 연결된 모든 정점, 그리고 그 정점들만 방문합니다.

큐에 넣을 때 visited를 갱신하므로 중복 간선과 자기 루프는 큐 길이를 부풀리지 않습니다. BFS가 끝나면 queue.length가 해당 구역의 정점 수입니다. 큐의 head가 끝까지 이동했어도 배열에 발견된 정점들이 남아 있으므로 별도의 count 없이 이 길이를 사용할 수 있습니다.

전체 탐색 후 숫자 비교 함수 (a,b) => a-b로 크기를 정렬합니다. 기본 sort는 문자열 기준이므로 10과 2 같은 크기에서 잘못된 순서를 만들 수 있습니다. 서로 다른 구역이 같은 크기를 갖는 것은 정상이라 중복 크기를 제거하지 않습니다.

복잡도: 마지막 정렬도 포함합니다

짧은 식별자의 Map/Set 접근과 배열 append를 기대·상환 O(1)로 보는 모델에서 그래프 구축과 전체 BFS는 O(V+E)입니다. 연결 구역 수를 c라고 하면 마지막 정렬 O(c log(c+1))을 더해 총 O(V+E+c log(c+1))입니다. 출력 정렬이 있는데 전체를 무조건 O(V+E)라고 줄이지 않습니다.

인접 리스트는 O(V+E), visited는 O(V), 한 구역의 누적 큐는 최대 O(V), 결과는 O(c)입니다. 입력 JSON과 식별자 문자열 총길이 C를 포함한 전체 공간은 O(V+E+C)입니다. 처리한 큐 항목을 즉시 제거하지 않으므로 큐가 순간 경계 폭만큼의 공간이라는 주장은 이 구현과 맞지 않습니다.

직접 확인할 경계

빈 그래프, 정점만 있고 간선 없음, 모든 정점이 한 구역, 중복 간선, 자기 루프, 크기 2와 크기 10인 두 구역을 확인하세요. 작은 무작위 그래프에서는 인접 행렬의 전이 폐쇄로 연결 관계를 구한 결과와 비교하면 BFS 구현과 독립적으로 구역 크기를 검증할 수 있습니다.