백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 24479 , 지름길

백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 24479 , 지름길

 

 

 

풀이 시간

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
JS 푸는거 뭔가 겁나 재밌다 !! ㅋㅋ 어지간하면 함수형으로 풀려고 한다.

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

 

 

 

정답

 

 

 

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

const dijkstra = (start) => {
  for (let [next, cost] of graph[start]) {
    if (dist[next] > dist[start] + cost) {
      dist[next] = dist[start] + cost;
    }
  }
  return;
};

const [N, D] = input.shift().split(" ").map(Number);
const graph = [...new Array(D + 1)].map(() => []);
const dist = [...new Array(D + 1)].fill(Infinity);

for (let i = 0; i < N; i++) {
  const [start, end, len] = input.shift().split(" ").map(Number);
  if (end > D) continue;
  if (end - start > len) {
    graph[start].push([end, len]);
  }
}

let tmp = -1;
for (let j = 0; j < D + 1; j++) {
  if (j > 0) tmp = dist[j - 1];
  dist[j] = Math.min(dist[j], tmp + 1);
  if (graph[j].length > 0) dijkstra(j);
}

console.log(dist[D]);