[백준1446_자바스크립트(javascript)] - 지름길

🔴 문제

지름길

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, d], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const dp = Array(d + 1)
  .fill(0)
  .map((_, idx) => idx);

const shortcuts = new Map();

for (const [s, e, c] of inputs) {
  if (!shortcuts.has(s)) shortcuts.set(s, [[e, c]]);
  else shortcuts.set(s, [...shortcuts.get(s), [e, c]]);
}

for (let i = 0; i <= d; i++) {
  if (i) dp[i] = Math.min(dp[i - 1] + 1, dp[i]);

  if (shortcuts.has(i)) {
    for (const [e, c] of shortcuts.get(i)) {
      if (e <= d) dp[e] = Math.min(dp[e], dp[i] + c);
    }
  }
}

console.log(dp.at(-1));

🟢 풀이

⏰ 소요한 시간 : -

다익스트라, dp 등 여러 알고리즘으로 풀 수 있는 문제인데 나는 dp로 풀이했다.
dp[n]은 시작점에서 n까지 최소로 운전해야 하는 거리이다.
만약 지름길이 없다면 dp[n]은 n의 값을 가질테니 인덱스번호로 초기화를 해준다.
그 후 지름길 정보를 map객체로 저장해주었다.

이제 시작점 0부터 목적지 d까지 dp배열을 업데이트 해주면 되는데, 먼저 i가 0이 아닌경우에만 dp[i]는 이전 위치에서 1움직인 dp[i - 1] + 1와 dp[i] 중 최소값을 고르면 된다.
그 후 현재 위치에서 지름길로 이동할 수 있다면 이동할 수 있는 모든 지름길을 탐색해 최소값으로 업데이트 해준다.

🔵 Ref