문제 개요

문제: 웜홀

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

난이도: 골드3

문제 풀이

플로이드 와샬 알고리즘을 통해 풀이했다.

도로는 양방향 이동이 가능하고 웜홀은 단방향 이동만 가능하다는 점에 주의하여 최단 시간을 저장하는 dist 배열을 초기화한다.

이후 플로이드 와샬 알고리즘으로 dist 배열을 채우고, 어느 지점 i에 대해 dist[i][i]가 음수라면 출발했을 때보다 시간이 되돌아가 있는 경우이므로 “YES”를 출력한다.
그렇지 않다면 “NO”를 출력한다.

코드

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

const solution = () => {
  const answer = [];

  for (let t = 0; t < input.length; ) {
    const [N, M, W] = input[t].split(" ").map(Number);
    const dist = Array.from({ length: N + 1 }, () =>
      new Array(N + 1).fill(Infinity)
    );

    // 도로와 웜홀을 edges 배열에 저장한다.
    input.slice(t + 1, t + M + 1).forEach((v) => {
      const [from, to, time] = v.split(" ").map(Number);
      // 도로는 양방향 이동이 가능하다.
      dist[from][to] = Math.min(dist[from][to], time);
      dist[to][from] = Math.min(dist[to][from], time);
    });

    input.slice(t + M + 1, t + M + W + 1).forEach((v) => {
      const [from, to, time] = v.split(" ").map(Number);
      // 웜홀은 단방향 이동만 가능하다.
      dist[from][to] = Math.min(dist[from][to], -time);
    });

    for (let k = 1; k <= N; k++) {
      for (let i = 1; i <= N; i++) {
        for (let j = 1; j <= N; j++) {
          if (dist[i][j] > dist[i][k] + dist[k][j])
            dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }

    let result = "NO";
    for (let i = 1; i <= N; i++) {
      if (dist[i][i] < 0) {
        result = "YES";
        break;
      }
    }

    answer.push(result);
    t += 1 + M + W;
  }

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

solution();