크래프톤 정글 주제별 탐구 -다익스트라 알고리즘-

정의

다익스트라 알고리즘은 DP(혹은 그리디)를 이용하여, 노드와 노드 사이의 최단 경로를 구하는 알고리즘이다.

동작 방식

간단한 다익스트라 알고리즘의 작동 방식에 대해 알아보자.

1. 모든 노드의 이동 경로를 일단 나와있는 대로 2차원 배열을 통해 저장한다.
2. 출발 노드를 설정한다.
3. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
4. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
5. 해당 노드를 거쳐서 특정한 노드로 가는 경우의 비용이 특정 노드로 바로 가는 것보다 저렴하다면 최소 비용을 갱신한다.
6. 4~5를 반복한다.

---

구현

```