[백준 / JS ] 1446 지름길

Problem | 1446 지름길

🕊 난이도

실버 1

📣 풀이 방법

// 예제
5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

1. 단방향 그래프를 구성한다.
   

• 이 때 지름길인 길만 graph 배열에 추가해준다.

  start =0 , end = 50, 지름길 길이 = 60 이면 안가는 것이 낫다.

• 최종 d 값보다 end 값이 넘는다면 그래프에 추가 하지 않는다.

  예제에서 만약 100에서 출발해서 151에 도착하는 길은 선택할 수 없다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 역주행 할 수 없기 때문이다.

2. dist 배열을 생성하여 0 부터 d 까지 순회한다.

• prev = dist [i-1] 값으로 설정하여 지름길을 이용하지 않는 방식은 dist[i-1]+1 의 방법이다.
• i에서 출발하는 지름길이 있다면 현재까지 온 거리 + 지름길의 거리(cost)를 더해서 dist[도착 지점] 보다 작다면 값을 갱신해준다.

📄 전체 풀이

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

const [n, d] = inputs[0].split(" ").map(Number);
let dist = Array.from(Array(d + 1).fill(Infinity));
const graph = Array.from(Array(d + 1), () => []);

for (let i = 0; i < n; i++) {
  const [start, end, w] = inputs[i + 1].split(" ").map(Number);
  if (end > d) continue;
  if (end - start <= w) continue;

  graph[start].push([end, w]);
}

let prev = -1;
for (let i = 0; i <= d; i++) {
  if (i) prev = dist[i - 1];

  dist[i] = Math.min(dist[i], prev + 1);

  for (let [next, cost] of graph[i]) {
    if (dist[next] > dist[i] + cost) {
      dist[next] = dist[i] + cost;
    }
  }
}
console.log(dist[d]);