프로그래머스 Lv.2: 배달

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

다익스트라를 사용하지 않는다면 모든 테스트케이스가 풀리지 않는 문제이다.
나는 DFS 를 이용하여 짧은 경로를 찾는 식으로 풀었는데 모든 테스트케이스를 통과하려면 다익스트라를 사용해야 해서 직접 공부해서 풀었다.

다익스트라를 애니메이션으로 정말 쉽게 설명한 영상:
https://www.youtube.com/watch?v=EFg3u_E6eHU&t=221s

function solution(N, road, K) {
    var answer = 0;
  
    // 1. 인접행렬을 만든다.
    // N의 범위는 50이므로 50*50 은 충분히 만들만 하다.
    let graph = Array(N+1).fill(0).map(e=>Array(N+1).fill(Infinity))
    for (let [a,b,c] of road) {
        if (c >= graph[a][b]) continue;
        graph[a][b] = c;
        graph[b][a] = c;
    }
  
    // 2. 자기 자신은 0 으로 만들어준다.
    for (let i = 1; i <= N; i++){
        graph[i][i] = 0;
    }
  
    let check = Array(N+1).fill(0); // 방문 체크용 배열
    let dist = Array(N+1).fill(Infinity); // 최단 거리 배열
    
    // 3. 다익스트라 알고리즘으로 1번 마을에서 다른 마을까지의 최단경로를 찾는다.
  
    // 방문하지 않은 노드 중에서 현재 위치에서 가장 가까운 노드의 
    // 인덱스를 반환하는 함수이다.
    function nearestNodeIdx(){
        let min = Infinity;
        let idx = 0;
        for (let i = 1; i <= N; i++){
            if (!check[i] && dist[i] < min){
                min = dist[i];
                idx = i;
            } 
        }
        return idx;
    }
  
    let start = 1; // 시작 위치
  
    // 1번 노드와 연결되어 있는 노드와의 거리를 넣는다.
    for (let i = 1; i <= N; i++){
        dist[i] = graph[start][i]
    }
  
    check[start] = 1;
  
    for (let i = 1; i <= N; i++){
        let current = nearestNodeIdx();
        check[current] = 1;
        for (let j = 1; j <= N; j++){
            if (!check[j]) {
                // 새로운 거리가 기존의 거리보다 짧으면 교체
                let oldd = dist[j];
                let newd = dist[current] + graph[current][j]
                if (newd < oldd) {
                    dist[j] = newd;
                }
            }
        }
    }
  
    answer = dist.filter(e => e <= K).length;
    return answer;
}