[백준11657_자바스크립트(javascript)] - 타임머신

🔴 문제

타임머신

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, k], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const distance = Array(n + 1).fill(Infinity);

distance[1] = 0;

let hasNegativeCycle = false;
for (let i = 1; i <= n; i++) {
  for (const [a, b, c] of inputs) {
    if (distance[b] > distance[a] + c) {
      distance[b] = distance[a] + c;

      if (i === n) hasNegativeCycle = true;
    }
  }
}

if (hasNegativeCycle) console.log(-1);
else {
  for (let i = 2; i <= n; i++) {
    console.log(distance[i] === Infinity ? -1 : distance[i]);
  }
}

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 벨만 포드 알고리즘의 기본 유형이다.
벨만 포드 알고리즘은 최단거리를 찾는 방법중 하나인데 음수 가중치를 가지는 경우 사용한다.
벨만 포드 알고리즘을 사용하게 되면 한 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있다.
이 때 세 개 이상의 정점이 싸이클을 형성하고, 음수 가중치를 가지게 되어 싸이클을 돌면 돌수록 최단거리가 갱신되는 경우가 생겨 싸이클을 판별하는데 사용되기도 한다.

벨만 포드 알고리즘은 다음과 같은 방식으로 풀이한다.

1. 출발 노드를 지정하고, 최단거리 테이블을 무한으로 초기화한다.
2. n-1 번동안 전체 간선 정보를 확인하며 최단거리 테이블을 갱신한다.
3. n-1 번의 순회를 마친 후, 한 번 더 순회하여 최단 거리가 생기는 경우 음수 싸이클이 발생한 경우임을 알 수 있다.

만약 음수 싸이클이 없다면 2번의 결과값이 최단거리가 되지만, 음수 싸이클이 있다면 결과값이 달라지기 때문에 3번의 과정을 통해 확인을 해주어야 한다.

다시 문제로 돌아와서, 타임머신 문제의 경우 1번 도시에서 시작해서 나머지 도시로 가는 가장 빠른 시간을 구하는데 시간이 음수일 수 있어서 벨만 포드 알고리즘을 사용하면 된다.
만약 시간을 무한이 오래 전으로 되돌릴 수 있다면 이라는 말이 나왔으므로 음수사이클이 존재할 수 있다고 해석하면 된다.

그래서 최단거리 테이블을 Infinity로 초기화 해 주고, 시작 노드인 1번노드의 최단거리를 0으로 둔뒤
n-1번 반복하면서 모든 간성정보를 순회하며 최단거리를 갱신한다.
위 과정을 마친 후 한번 더 돌아서 최단거리가 업데이트 되는지를 확인해야 하기 때문에 나는 처음 for문의 범위를 n까지로 설정해주었고, 음수사이클 존재여부를 확인하는 hasNegativeCycle이라는 트리거변수를 만들어주었다.

마지막으로 결과를 출력해주면 끝

🔵 Ref