[JavaScript] 백준 11657번: 타임머신 (벨만 포드)

난이도 : 골드 4
알고리즘 유형 : 벨만 포드
문제 링크 : https://www.acmicpc.net/problem/11657

 

 

문제 풀이

• 한 정점에서 다른 모든 정점으로의 최단 거리 테이블 구성
• 음의 순환이 있는지 확인

위 두가지의 경우를 확인할 수 있는 알고리즘은 벨만 포드와 SPFA가 있다.

 

이번 문제에서는 벨만 포드로 풀어볼 것이다.

 

벨만 포드는 정점의 갯수 - 1 만큼 간선들을 반복 연산하여 최단 거리 테이블을 갱신한다.

음의 순환이 없고, 단순히 최단 거리 테이블을 구하는 것이라면 위의 계산으로 최단 거리 테이블을 얻을 수 있다.

하지만 음의 순환이 있는지 확인하기 위해서는 한 번 더 간선들을 연산하였을 때, 테이블이 갱신되는 지 확인해야한다.

 

• 모든 간선들을 V - 1 만큼 반복하여 최단 거리 테이블 갱신.
• V번째 반복에서 테이블이 갱신되면 음의 순환 존재. (V : 정점의 갯수)

 

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BACKJOON_011657.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split(/\r?\n/);

const [N, M] = input.shift().split(" ").map(Number);
const edges = input.map((row) => row.split(" ").map(Number));

const time = Array.from({length: N + 1}, () => Infinity);
time[1] = 0;

for(let i=1; i<=N; i++){
  for(const [s, e, t] of edges) {
    if(i === N && time[e] > time[s] + t) { console.log(-1); return; }
    time[e] = Math.min(time[e], time[s] + t);
  }
}

time.slice(2).map((v) => v === Infinity ? -1 : v).forEach(v => console.log(v));

 

 

회고

저번에 벨만 포드 문제를 풀 때는 벨만 포드 알고리즘 자체를 몰라서 푸는데 시간이 오래 걸렸다.

하지만 이번에는 이미 알고있는 개념이라서 그런지 12분 만에 풀 수 있어서 알고리즘을 많이 알고 있는게 중요하다는 것을 다시 알게되었다.

 

이번에는 벨만 포드로 문제를 풀었지만 다음에는 SPFA로도 풀어봐야겠다!