[프로그래머스] 배달 / JavaScript / Level 2

🚩문제 주소

📄풀이

다익스트라 알고리즘

먼저 시간의 값을 저장할 배열과 주어진 정보를 그래프로 저장합니다.

q에 1번 마을과 시간 0을 저장하고 1번 시간을 0으로 저장합니다.
시작 마을에 연결된 마을들을 순회하는데,
연결된 마을의 저장되어 있는 시간이 현재 마을의 시간 + 연결된 마을의 시간보다 크면 연결된 마을의 저장되어 있는 시간을 갱신해주고 q에 push합니다.

시간 배열을 filter를 사용해서 K보다 작거나 같은 수만 남긴 다음 길이를 반환합니다.

👨‍💻코드

function solution(N, road, K) {
  const time = Array.from({ length: N + 1 }, () => 500001);
  const graph = Array.from({ length: N + 1 }, () => []);

  road.forEach((v) => {
    let [s, e, t] = v;
    graph[s].push({ to: e, time: t });
    graph[e].push({ to: s, time: t });
  });

  const q = [{ to: 1, time: 0 }];
  time[1] = 0;

  while (q.length) {
    let { to } = q.pop();

    graph[to].forEach((next) => {
      if (time[next.to] > time[to] + next.time) {
        time[next.to] = time[to] + next.time;
        q.push(next);
      }
    });
  }

  return time.filter((v) => v <= K).length;
}