[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 위치까지 가는 데 필요한 최단 거리
- 초기값 : 각 위치의 인덱스 값으로 초기화 (지름길을 사용하지 않았을 때의 거리)
 
식
각 위치 i에 대해:
1. 이전 위치에서 한 칸 이동 : dp[i] = min(dp[i], dp[i-1] + 1)
2. 지름길을 사용하는 경우 : dp[i] = min(dp[i], dp[from] + dist) 
 
전체 코드

// 입력 처리
const [n, d] = input[0].split(" ").map(Number);
const shortRoads = input.slice(1, d + 1).map((line) => line.split(" ").map(Number));

// 도착 지점 기준 정렬 (효율적인 계산을 위해)
shortRoads.sort((a, b) => a[1] - b[1]);

// dp 배열 초기화: 각 위치까지 기본 거리로 초기화
let dp = Array.from({ length: d + 1 }, (_, i) => i);

// 각 위치까지의 최단 거리 계산
for (let i = 1; i <= d; i++) {
  // 1. 이전 위치에서 한 칸 이동
  dp[i] = Math.min(dp[i], dp[i - 1] + 1);

  // 2. 지름길을 사용하는 경우
  shortRoads.forEach(([from, to, dist]) => {
    if (i === to) {
      dp[i] = Math.min(dp[from] + dist, dp[i]);
    }
  });
}