문제 개요

문제: 타임머신

분류: 그래프 이론, 최단 경로, 벨만-포드

난이도: 골드4

문제 풀이

타임머신으로 시간을 되돌아가는 경우도 있다는 것은 음의 간선이 존재한다는 말이다.
따라서 벨만포드 알고리즘을 통해 최소 시간을 구하고 음의 사이클 또한 확인한다.

음의 사이클이 존재한다면 -1을, 그렇지 않다면 2번 도시부터 N번 도시까지 가는 가장 빠른 시간을 순서대로 출력한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [NM, ...edge] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = NM.split(" ").map(Number);

const solution = () => {
  const dist = Array(N + 1).fill(Infinity);
  const answer = [];

  const bellmanford = () => {
    dist[1] = 0;

    for (let i = 1; i < N; i++) {
      for (let j = 0; j < edge.length; j++) {
        const [from, to, time] = edge[j].split(" ").map(Number);

        if (dist[from] === Infinity) continue;
        if (dist[to] > dist[from] + time) dist[to] = dist[from] + time;
      }
    }

    // 음의 사이클 확인
    for (let j = 0; j < edge.length; j++) {
      const [from, to, time] = edge[j].split(" ").map(Number);

      if (dist[from] === Infinity) continue;
      // 변화가 있다면 음의 사이클이 존재하는 것
      // =시간을 무한히 오래 전으로 되돌릴 수 있으므로 -1 출력
      if (dist[to] > dist[from] + time) {
        answer.push(-1);
        return;
      }
    }
  };

  bellmanford();

  // 정답 배열에 이미 뭔가 있다면 -1이 저장되어 있다는 의미이므로 종료
  if (answer.length > 0) {
    console.log(-1);
    return;
  }

  for (let i = 2; i <= N; i++) {
    if (dist[i] === Infinity) answer.push(-1);
    else answer.push(dist[i]);
  }

  console.log(answer.join("\n"));
};

solution();