프로그래머스 레벨 2의 배달 문제(12978)는 마을 개수 N, 두 마을 사이의 거리 정보 road, 배달 가능한 시간(거리) K를 인자로 받아, 1번 마을에 있는 음식점이 K이하 시간에 배달할 수 있는 마을의 개수를 반환해야 한다.
N : 1 ≤ N ≤ 50[[a, b, c], [...]]
a b : 두 마을의 번호c : 두 마을의 거리(시간)K : 1 ≤ K ≤ 500,000
이미지 출처 : 프로그래머스
왼쪽 마을 이미지를 기준으로 1번부터 5번 마을까지 최소 배달 시간을 [번호, 시간] 배열 형태로 나타내면 아래와 같다.
// [[번호, 시간], [...]]
[[1, 0], [2, 1], [3, 4], [4, 2], [5, 3]]
만약 배달 가능한 시간 K가 3이라면 1, 2, 4, 5번 마을이 모두 3시간 이하여서 정답은 4가 된다.
이처럼 1번 마을에서 다른 모든 마을까지 소요되는 최단 거리(시간)를 계산해야만 정답을 구할 수 있다. 1번 마을에서 1번 마을까지의 거리는 항상 0으로 취급한다. 이 문제는 다익스트라 알고리즘을 활용하면 해결할 수 있다.
다익스트라 알고리즘은 최단 경로를 계산할 때 사용하는 가장 대표적인 알고리즘 중 하나로 길찾기 등 현실 세계에서 자주 활용된다. 알고리즘의 동작 과정은 아래와 같다.
<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 그리디 알고리즘은 매 선택에서 지역적으로 최적의 선택을 통해 전역적인 최적해를 구하는 방식이다
</aside>
다익스트라 알고리즘은 매 상황에서 거리가 가장 짧은(비용이 가장 적은) 노드를 선택하는 과정을 반복한다는 점에서 그리디 알고리즘으로 분류한다. 이미 계산한 최단 경로를 저장하고 재활용하는 점에 있어 다이나믹 프로그래밍과 유사한 면도 있다.
다익스트라 알고리즘은 거리 배열(Distance Array), 탐색 큐(Search Queue), 인접 리스트(Adjacency List) 이렇게 3가지를 기반으로 동작한다.