[프로그래머스] 배달

문제

Summer/Winter Coding(~2018) - 배달

https://school.programmers.co.kr/learn/courses/30/lessons/12978

 

 

풀이

설명

1번 마을에서 K 시간 내에 배달 가능한 마을의 개수를 구하는 문제입니다.

 

1번 마을에서 각 마을까지 걸리는 최단 시간을 구하면 됩니다.

다익스트라 알고리즘을 사용해서 해결 가능합니다.

 

예시 코드

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

  for (const [a, b, weight] of road) {
    graph[a].push({ adjacentNode: b, weight });
    graph[b].push({ adjacentNode: a, weight });
  }

  const shortestDistances = Array(N + 1).fill(Infinity);
  shortestDistances[1] = 0;

  const pq = new PriorityQueue();
  pq.enqueue(1, 0);

  // 다익스트라 알고리즘
  while (!pq.isEmpty()) {
    const { value: currentNode, priority: currentDistance } = pq.dequeue();

    if (currentDistance > shortestDistances[currentNode]) continue;

    for (let i = 0; i < graph[currentNode].length; i++) {
      const { adjacentNode, weight } = graph[currentNode][i];
      const newDistance = shortestDistances[currentNode] + weight;
      if (newDistance >= shortestDistances[adjacentNode]) continue;

      shortestDistances[adjacentNode] = newDistance;
      pq.enqueue(adjacentNode, newDistance);
    }
  }

  return shortestDistances.filter((d) => d <= K).length;
}