코딩테스트 고급: 최소 힙으로 다익스트라 최단 경로 구하기

1. 그래프와 우선순위 큐를 준비합니다

graph[u]에 [v, w]를 저장하면 u에서 나가는 간선만 확인할 수 있습니다. 일반 큐는 들어온 순서대로 꺼내지만, 이 문제의 우선순위 큐는 [현재까지의 비용, 정점] 중 비용이 가장 작은 항목을 꺼냅니다. 모든 간선의 비용이 같지 않으므로 간선 개수가 적은 경로가 최소 비용이라는 보장은 없습니다.

최소 힙은 배열로 저장하는 완전 이진 트리입니다. 인덱스 i의 부모는 floor((i-1)/2), 자식은 2i+1과 2i+2입니다. 부모 비용이 두 자식 비용보다 작거나 같게 유지하면 맨 앞에 최솟값이 옵니다. 삽입은 끝에 놓고 부모 방향으로 올리고, 삭제는 마지막 값을 루트 자리에서 작은 자식 방향으로 내립니다. 같은 비용의 정점은 어느 것을 먼저 꺼내도 됩니다. 이 구현은 자식 중 더 작은 쪽을 고르며 힙 전체를 정렬하지 않습니다. 힙의 기본 원리는 Princeton Algorithms: Priority Queues를 참고했습니다.

2. 거리 갱신과 오래된 후보 처리를 분리합니다

dist[S]만 0, 나머지는 Infinity로 시작합니다. 비용 cost인 정점 u에서 간선 (u, v, w)를 확인할 때 cost+w가 dist[v]보다 작으면 거리와 후보를 갱신합니다. 이를 완화(relaxation)라고 부릅니다. 더 짧아진 경우에만 넣는 엄격한 비교가 필요합니다. 같을 때도 다시 넣으면 0 비용 순환에서 같은 후보가 끝없이 생길 수 있습니다.

이 코드는 힙 내부 항목을 찾아 값을 줄이는 decrease-key 대신 새 후보를 삽입합니다. 예제에서 [10, 2]를 먼저 넣어도 나중에 [5, 2]가 생깁니다. [5, 2]를 확장한 뒤 [10, 2]가 나오면 cost !== dist[vertex]로 버립니다. 오래된 후보에서 간선을 다시 읽지 않아 반복 작업을 막습니다.

3. 왜 최소 후보를 꺼내도 안전한가요?

유효한 최소 후보 u보다 더 짧은 미발견 경로가 있다고 가정해 봅니다. 그 경로에서 이미 처리한 영역을 처음 벗어나는 정점 x는 앞선 간선 완화로 후보가 되었어야 합니다. 남은 가중치가 모두 0 이상이므로 x까지의 비용은 그 더 짧은 경로 전체보다 클 수 없습니다. 그러면 u보다 작은 후보 x가 먼저 나와야 하므로 모순입니다. 따라서 유효한 최소 후보의 거리는 확정할 수 있습니다. 정의와 알고리즘의 비음수 조건은 Princeton Algorithms: Shortest Paths에서 확인할 수 있습니다.

음수 간선이 있으면 위 근거가 성립하지 않습니다. 예를 들어 1→2가 2, 1→3이 5, 3→2가 -10이면 먼저 나온 2의 비용 2가 최종 최솟값이 아닙니다. 이 글의 solve는 음수 간선을 거부합니다. dijkstra 함수 자체는 검증을 통과한 비음수 그래프를 받는 내부 함수입니다. 음수를 처리하려면 Bellman-Ford 등 조건에 맞는 알고리즘과 음수 순환 정책을 별도로 설계해야 합니다.

4. Node.js 표준 입력 전체 코드

아래 코드를 algorithm-advanced.cjs로 저장합니다. 외부 패키지는 필요 없습니다. readFileSync(0, 'utf8')로 표준 입력을 읽고, 공백·탭·LF·CRLF를 같은 토큰 경계로 처리합니다. 읽기 API는 Node.js 공식 파일 시스템 문서를 따릅니다. 잘못된 입력은 표준 출력 없이 stderr와 종료 코드 1로 알립니다. .cjs 확장자는 CommonJS 실행을 명시합니다.

'use strict';
const fs = require('node:fs');

class MinHeap {
  constructor() { this.items = []; }
  get size() { return this.items.length; }
  push(entry) {
    const a = this.items;
    a.push(entry);
    let i = a.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (a[parent][0] <= entry[0]) break;
      a[i] = a[parent];
      i = parent;
    }
    a[i] = entry;
  }
  pop() {
    const a = this.items;
    if (a.length === 0) return undefined;
    const root = a[0];
    const last = a.pop();
    if (a.length === 0) return root;
    let i = 0;
    while (i * 2 + 1 < a.length) {
      let child = i * 2 + 1;
      if (child + 1 < a.length && a[child + 1][0] < a[child][0]) child++;
      if (last[0] <= a[child][0]) break;
      a[i] = a[child];
      i = child;
    }
    a[i] = last;
    return root;
  }
}

function dijkstra(graph, start) {
  const dist = Array(graph.length).fill(Infinity);
  const heap = new MinHeap();
  dist[start] = 0;
  heap.push([0, start]);
  while (heap.size > 0) {
    const [cost, vertex] = heap.pop();
    if (cost !== dist[vertex]) continue; // 예전 거리의 항목은 확장하지 않습니다.
    for (const [next, weight] of graph[vertex]) {
      const candidate = cost + weight;
      if (candidate < dist[next]) {
        dist[next] = candidate;
        heap.push([candidate, next]);
      }
    }
  }
  return dist;
}

function solve(input) {
  const text = input.trim();
  if (!text) throw new Error('입력이 비었습니다.');
  const raw = text.split(/\s+/);
  if (!raw.every(token => /^-?\d+$/.test(token))) {
    throw new Error('정수 토큰만 허용합니다.');
  }
  const tokens = raw.map(Number);
  if (!tokens.every(Number.isSafeInteger)) throw new Error('안전한 정수가 아닙니다.');
  const [n, m, start] = tokens;
  if (!(n >= 1 && n <= 20000 && m >= 0 && m <= 200000 &&
        start >= 1 && start <= n && tokens.length === 3 + 3 * m)) {
    throw new Error('정점·간선 개수 또는 시작점이 올바르지 않습니다.');
  }
  const graph = Array.from({ length: n + 1 }, () => []);
  for (let i = 3; i < tokens.length; i += 3) {
    const [from, to, weight] = tokens.slice(i, i + 3);
    if (!(from >= 1 && from <= n && to >= 1 && to <= n &&
          weight >= 0 && weight <= 1000000)) {
      throw new Error('정점 범위 또는 가중치가 올바르지 않습니다. 음수 간선은 허용하지 않습니다.');
    }
    graph[from].push([to, weight]); // 방향 간선이므로 역방향은 추가하지 않습니다.
  }
  return dijkstra(graph, start).slice(1)
    .map(value => value === Infinity ? 'INF' : String(value)).join('\n');
}

if (require.main === module) {
  try {
    process.stdout.write(solve(fs.readFileSync(0, 'utf8')) + '\n');
  } catch (error) {
    process.stderr.write(error.message + '\n');
    process.exitCode = 1;
  }
}
module.exports = { MinHeap, dijkstra, solve };

입력 예제를 input.txt로 저장한 뒤 Windows 명령 프롬프트 또는 Bash에서 아래와 같이 실행합니다. PowerShell에서는 Get-Content -Raw -Encoding UTF8 .\input.txt | node .\algorithm-advanced.cjs를 사용할 수 있습니다. 답 이외의 디버깅 문장을 표준 출력에 추가하지 마세요.

node algorithm-advanced.cjs < input.txt

5. 시간·공간 복잡도와 숫자 범위

유효한 후보에서 각 정점의 나가는 간선을 한 번씩 확인합니다. 성공한 완화는 최대 M번이고, 시작점까지 포함해 힙 삽입·삭제는 O(M+1)번입니다. 오래된 후보도 남기므로 힙 최대 크기는 O(M+1)이며, 힙 연산은 O(log(M+2))입니다. 정점 초기화·출력까지 포함한 시간은 O(N + (M+1) log(M+2)), 인접 리스트·거리·힙·입력 토큰을 포함한 공간은 이 제한에서 O(N+M)입니다. M=0에서도 초기화와 출력 O(N)이 필요합니다.

다중 간선을 허용하는 이 구현을 무조건 O(M log N), 힙 공간 O(N)이라고 적지 않습니다. 별도의 인덱스 힙으로 정점당 후보 하나만 유지하는 구현과 구분해야 합니다. 정수의 자릿수가 고정되어 있지 않다면 파싱에 입력 문자열 길이 L에 따른 시간·공간 비용도 추가해야 합니다.

비음수 그래프의 최단 경로는 순환을 제거한 단순 경로로 고를 수 있습니다. 따라서 최단거리 최댓값은 (N-1)×1,000,000=19,999,000,000이고 Number의 안전한 정수 범위 안입니다. 후보 덧셈도 N×1,000,000 이하입니다. 32비트 정수 범위는 넘을 수 있으므로 비용에 비트 연산이나 | 0을 쓰면 안 됩니다. 제한을 늘리면 안전 정수 범위를 다시 계산하세요.

6. 경계 테스트와 완료 기준

검증 파일 algorithm-advanced.test.cjs는 고정 사례 7개를 LF·CRLF로 검사하고 실제 Node 프로세스 14회에서 stdout·stderr·종료 코드를 확인합니다. 잘못된 입력 7개, 힙의 빈 상태·중복 우선순위, 오래된 후보의 인접 리스트 재방문 방지, 최대 N·M도 검사합니다. 시드 20260910의 작은 무작위 그래프 500개는 독립적인 Bellman-Ford 기준 풀이와 비교합니다. HTML에 실린 코드와 실행 파일이 같은지도 검사합니다. 함께 제공된 테스트 파일을 같은 폴더에 두고 node algorithm-advanced.test.cjs로 재현할 수 있습니다.

완료 기준은 예제 출력이 맞는 것에 더해, 음수 간선을 허용하지 않는 이유, 오래된 후보를 버리는 이유, 도달 불가 출력, 다중 간선을 포함한 복잡도를 자신의 말로 설명하는 것입니다. 추가 연습으로 예제의 간선 하나를 제거하고 거리 변화를 손으로 예상한 뒤 실행 결과와 비교해 보세요.

검증 기록: 2026-09-10, Node.js v24.18.0에서 위 검증을 모두 통과했습니다. 아래를 algorithm-advanced.test.cjs로 저장하면 재현할 수 있습니다. HTML 동기화 검사는 작성자 검토용이므로 아래 독자용 테스트에서는 제외했습니다.

'use strict';
const assert = require('node:assert/strict');
const { spawnSync } = require('node:child_process');
const path = require('node:path');
const fs = require('node:fs');
const { MinHeap, dijkstra, solve } = require('./algorithm-advanced.cjs');
const cases = [
 ['example', '6 8\n1\n1 2 10\n1 3 2\n3 2 3\n2 4 1\n3 4 9\n4 5 0\n1 5 20\n3 5 15\n', '0\n5\n2\n6\n6\nINF'],
 ['single', '1 0\n1', '0'],
 ['no edges / non-one start', '3 0\n2', 'INF\n0\nINF'],
 ['zero cycle', '3 3\n1\n1 2 0\n2 1 0\n2 3 0', '0\n0\n0'],
 ['parallel edges / self-loop', '3 4\n1\n1 1 0\n1 2 9\n1 2 2\n2 3 4', '0\n2\n6'],
 ['direction', '2 1\n2\n1 2 7', 'INF\n0'],
 ['equal candidates', '4 4\n1\n1 2 1\n1 3 1\n2 4 1\n3 4 1', '0\n1\n1\n2'],
];
for (const [name, input, expected] of cases) {
  for (const variant of [input, input.replace(/\n/g, '\r\n')]) {
    assert.equal(solve(variant), expected, name);
    const run = spawnSync(process.execPath, [path.join(__dirname, 'algorithm-advanced.cjs')], { input: variant, encoding: 'utf8' });
    assert.equal(run.status, 0, name);
    assert.equal(run.stdout, expected + '\n', name);
    assert.equal(run.stderr, '', name);
  }
}
const invalid = ['', '2 1 1 1 2 -1', '2 1 1 1 2', '2 0 3', '2 1 1 1 3 2', '2 1 1 1 2 1.5', '2 1 1 1 2 1000001'];
for (const input of invalid) assert.throws(() => solve(input));
const rejected = spawnSync(process.execPath, [path.join(__dirname, 'algorithm-advanced.cjs')], { input: invalid[1], encoding: 'utf8' });
assert.equal(rejected.status, 1);
assert.equal(rejected.stdout, '');
assert.match(rejected.stderr, /음수 간선/);
const heap = new MinHeap();
assert.equal(heap.pop(), undefined);
for (const cost of [5, 1, 9, 1, 0, 6, 2]) heap.push([cost, cost]);
assert.deepEqual(Array.from({length: 7}, () => heap.pop()[0]), [0, 1, 1, 2, 5, 6, 9]);
// 독립 기준 풀이: 모든 간선을 N-1번 완화하는 Bellman-Ford.
function reference(n, edges, start) {
 const d = Array(n + 1).fill(Infinity); d[start] = 0;
 for (let k = 1; k < n; k++) {
  for (const [u, v, w] of edges) d[v] = Math.min(d[v], d[u] + w);
 }
 return d;
}
let seed = 20260910;
function random(n) { seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0; return seed % n; }
for (let k = 0; k < 500; k++) {
 const n = 1 + random(9), m = random(50), start = 1 + random(n);
 const edges = Array.from({length: m}, () => [1 + random(n), 1 + random(n), random(21)]);
 const graph = Array.from({length: n + 1}, () => []);
 for (const [u,v,w] of edges) graph[u].push([v,w]);
 assert.deepEqual(dijkstra(graph, start), reference(n, edges, start));
}
// stale entry가 인접 리스트를 재확장하지 않는지 실제 방문 횟수 확인.
let visits = 0;
const g = [[], [[2, 10], [3, 1]], [], [[2, 1]]];
g[2] = { *[Symbol.iterator]() { visits++; } };
dijkstra(g, 1);
assert.equal(visits, 1);
// 최대 정점 수와 가중치: 32비트 범위를 초과하는 정상 최단거리.
const n = 20000;
const chain = Array.from({length: n - 1}, (_, i) => (i + 1) + ' ' + (i + 2) + ' 1000000');
assert.equal(solve(n + ' ' + (n - 1) + '\n1\n' + chain.join('\n')).split('\n').at(-1), '19999000000');
// 최대 간선 수와 다중 간선.
const many = Array.from({length: 200000}, (_, i) => '1 2 ' + (200000 - i)).join('\n');
assert.equal(solve('2 200000\n1\n' + many), '0\n1');
// HTML 동기화 검사는 작성자의 로컬 초안 검증에서 별도로 실행했습니다.
console.log('PASS: 7 fixed cases x LF/CRLF; 14 CLI runs; 7 invalid; heap; 500 Bellman-Ford comparisons; stale-entry; max V/E');