[프로그래머스] Lv2. 배달- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 배달

문제

제한사항

📌 내가 생각한 풀이

다익스트라 알고리즘 문제다. 여기서 가는길이 여러개인 경우가 있지만, 무조건 가장 가중치가 작은 길을 선택해주면 되기때문에, 가장 작은 길을 가중치로 선택해서 넣어주면 된다.

const getMin = (arr, visi)=>{
    let isVisited = visi
    let min  = Infinity;
    let idx = 0;
    for(var i=1; i<=arr.length; i++){
        if(arr[i] < min && !isVisited[i]){
            min = arr[i]
            idx = i;
        }
    }
    return [min,idx]
}

function solution(N, road, K) {
    var answer = 0;
    let arr = Array.from(Array(N+1), ()=>Array(N+1).fill(Infinity))
    let visited = new Array(N+1).fill(false);
    
    for(var k = 1; k<=N; k++){
        arr[k][k] = 0;
    }
    visited[1] = true;
    road.forEach((data,idx)=>{
        let [x, y, value] = data;
        arr[x][y] = Math.min(arr[x][y], value)
        arr[y][x] = Math.min(arr[y][x], value);
    })
    let weight = arr[1];
    let count = 0;
    let min =0;
    let end = N;
    while(count < end-1){
        let [minVal,idx] = getMin(weight, visited);
        let selectedArr = arr[idx];
        for(var k = 1; k<=N; k++){
            if(weight[k] > selectedArr[k] + minVal && !visited[k]){
                weight[k] = selectedArr[k] + minVal
            }
        }
        visited[idx] = true;
        count++;
    }
    return weight.filter((d)=> d <= K).length
}

📌 느낀점

다익스트라 알고리즘을 실제로 구현해본적이 없어서 조금 오래 걸렸던 문제이다. 원리를 이해하고 구현을 해보니, 만만치 않은 알고리즘이라고 생각되었다. 최소힙을 이용한 다익스트라 알고리즘도 정리해야겠다.