[JavaScript] 1446. 지름길

문제 설명
0부터 목적지(d)까지 가되, 가장 빠르게 갈 수 있는 거리를 찾는다.
만약 지름길이 없다면 거리는 d가 되지만, 중간에 지름길이 있다면 그 거리는 더 짧아진다.
 
예시

2 100
10 60 40
50 90 20

 
d가 100이고, 지름길이 총 2개이다.
 
- 0 -> 10 -> 60 ->  100 : 10 + 40 + 40 = 90
- 0 -> 50 -> 90 -> 100 : 50 + 20 + 10 = 80
 
이므로, 정답은 80이다.
 

문제 해결

이전 값이 이후 값에 영향을 주기 때문에, dp로 해결할 수 있었다.
 
DP 배열 정의
- dp[i] : i 위치까지 가는 데 필요한 최단 거리

- 0으로 초기화

 

식

각 위치 i에 대해,
기본적으로는 distance[i-1] + 1 을 수행한다.

하지만, 지름길을 사용하는 경우 그 거리는 더 짧아질 것이다.
만약 s -> e 로 가는 지름길이 있을 경우, 
distances[e] = Math.min(distances[e], distances[s] + d)

  
전체 코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim().split("\n");

const [N, D] = input[0].split(" ").map(Number);
const roads = input.slice(1, N + 1).map((line) => line.split(" ").map(Number));

const distances = Array.from({ length: D + 1 }, (_, i) => 0);

// i에 도착하는 경우에 대해
for (let i = 1; i <= D; i++) {
  distances[i] = distances[i - 1] + 1;
  for (let j = 0; j < N; j++) {
    const [s, e, d] = roads[j];

    if (i === e) {
      distances[e] = Math.min(distances[e], distances[s] + d);
    }
  }
}

console.log(distances[D]);