가장 저렴한 배송 경로 찾기

자바스크립트 코딩테스트 문제로 dijkstra 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium dijkstra 함수명: minimumDeliveryCost 제한 시간: 400ms

배송 허브와 양방향 도로 정보가 주어질 때, 한 허브에서 다른 허브까지 가는 가장 저렴한 배송 비용을 구하는 문제입니다.

문제 설명

허브는 0번부터 n - 1번까지 있습니다.

roads의 각 원소는 [a, b, cost] 형태이며, a번 허브와 b번 허브 사이를 비용 cost로 이동할 수 있다는 뜻입니다. 모든 도로는 양방향이고, 비용은 음수가 아닙니다.

start 허브에서 target 허브까지 이동하는 데 필요한 최소 비용을 반환하는 minimumDeliveryCost 함수를 작성하세요. 이동할 수 있는 경로가 없다면 -1을 반환합니다.

제한사항

1 <= n <= 100000
0 <= roads.length <= 200000
roads[i] = [a, b, cost]
0 <= a, b < n
a !== b
0 <= cost <= 100000
같은 두 허브 사이에 여러 도로가 있을 수 있습니다.
0 <= start, target < n
반환값은 start에서 target까지의 최소 비용입니다.
target에 도달할 수 없다면 -1을 반환합니다.

예시

입력: n = 5, roads = [[0, 1, 4], [0, 2, 2], [2, 1, 1], [1, 3, 3], [2, 3, 7], [3, 4, 1]], start = 0, target = 4 → 출력: 7
입력: n = 4, roads = [[0, 1, 5], [1, 2, 2]], start = 0, target = 3 → 출력: -1
입력: n = 3, roads = [[0, 1, 10], [0, 1, 3], [1, 2, 4], [0, 2, 20]], start = 0, target = 2 → 출력: 7
입력: n = 1, roads = [], start = 0, target = 0 → 출력: 0

힌트

도로 비용이 음수가 아니므로, 현재까지 비용이 가장 작은 후보를 먼저 확정하는 방식이 잘 맞습니다.
인접 리스트를 만들고, 우선순위 큐에는 [현재 비용, 허브]를 넣어 보세요.
이미 더 싼 비용으로 처리된 허브가 큐에서 다시 나오면 그 항목은 건너뛰어야 합니다.

해설

이 문제는 음수가 없는 가중 그래프에서 한 출발점의 최단 거리를 구하는 전형적인 다익스트라 알고리즘 문제입니다.

먼저 각 허브에서 이동할 수 있는 이웃 허브와 비용을 인접 리스트로 저장합니다. 그다음 dist[i]를 start에서 i번 허브까지 알려진 최소 비용으로 두고, 처음에는 모두 Infinity로 채웁니다. 출발점은 비용이 필요 없으므로 dist[start] = 0입니다.

우선순위 큐에는 현재까지 발견한 후보 경로를 넣습니다. 항상 비용이 가장 작은 후보를 꺼내고, 그 허브에서 이어지는 도로들을 확인합니다. 현재 허브까지의 비용에 도로 비용을 더한 값이 이웃 허브의 기존 dist보다 작다면 더 저렴한 경로를 찾은 것이므로 값을 갱신하고 큐에 다시 넣습니다.

같은 허브가 큐에 여러 번 들어갈 수 있다는 점이 중요합니다. 예를 들어 처음에는 비용 10으로 발견했다가 나중에 비용 3으로 더 좋은 경로를 찾을 수 있습니다. 이때 오래된 비용 10짜리 항목이 큐에서 나오면 dist에 저장된 최신 비용보다 크므로 바로 건너뛰면 됩니다.

모든 처리가 끝났을 때 dist[target]이 여전히 Infinity라면 도착지까지 이어지는 경로가 없다는 뜻이므로 -1을 반환합니다. 그 외에는 dist[target]이 최소 배송 비용입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과