[JS][프로그래머스]배달

문제 번호

프로그래머스

 

 

알고리즘 분류

•  다익스트라

문제 풀이

 문제를 읽어보면 1번 마을에서 다른 마을까지의 최소 경로를 알면 문제를 해결 할 수 있다는 것을 알 수 있다.

이것은 '한 정점에서 다른 모든 정점까지의 최소거리'를 구하는 다익스트라 알고리즘을 떠올리게 만든다. 다익스트라 알고리즘으로 1번 마을에서 다른 마을까지의 거리를 구하고 그 거리가 K이하가 되는 마을들을 모두 고르면 된다.

 

다익스트라를 사용하기 위해서 최소힙을 구현하자

class Node{
    constructor(node, dist){
        this.node = node;
        this.dist = dist;
    }
}
class MinHeap{
    constructor(compare) {
        this.compare = compare;
        this.heap = [];    
    }
    empty(){
        return !this.heap.length;
    }
    top(){
        return this.heap[0];
    }
    push(node, dist) {
        const newNode = new Node(node,dist);
        this.heap.push(newNode);
        if(this.heap.length > 0) {
            let curIdx = this.heap.length-1;
            let curItem = this.heap[curIdx];
            while(curIdx > 0) {
                const parentIdx = Math.floor((curIdx-1)/2);
                const parentItem = this.heap[parentIdx];
                
                if(this.compare(parentItem.dist, curItem.dist)) break;
                
                this.heap[curIdx] = parentItem;
                curIdx = parentIdx;
            }            
            this.heap[curIdx] = curItem;
        }
    }
    pop(){
        const lastIdx = this.heap.length-1;
        this.heap[0] = this.heap[lastIdx];
        this.heap.pop();
        if(this.heap.length > 0) {
            let curIdx = 0;
            let curItem = this.heap[curIdx];
            while(curIdx < this.heap.length) {
                const leftIdx = curIdx*2+1;
                const rightIdx = curIdx*2+2;
                
                if(leftIdx >= this.heap.length) break;
                
                const leftItem = this.heap[leftIdx];
                const rightItem = rightIdx < this.heap.length
                ? this.heap[rightIdx]
                : null;
                
                const nextIdx = rightItem !== null && this.compare(rightItem.dist, leftItem.dist)
                ? rightIdx
                : leftIdx;                
                const nextItem = this.heap[nextIdx];
                
                if(this.compare(curItem.dist, nextItem.dist)) break;
                
                this.heap[curIdx] = nextItem;
                curIdx = nextIdx;                
            }
            this.heap[curIdx] = curItem;
        }
    }
}

 

 이제 구현한 최소힙을 이용해서 다익스트라 알고리즘을 구현 해주면 된다.

 

전체 코드

function solution(N, road, K) {
    const graph = [];
    for(const [a,b,c] of road) {
        graph[a] = graph[a] || [];
        graph[b] = graph[b] || [];
        graph[a].push([b,c]);
        graph[b].push([a,c]);
    }
    return dijkstra(N,K,1,graph);
}
function dijkstra(N, K, start, graph){
    let ret = 0;
    
    const MH = new MinHeap((a,b)=>a<b);
    MH.push(start, 0) // node, dist
    const Distance = new Array(N+1).fill(Infinity);
    Distance[1] = 0;
    
    while(!MH.empty()) {        
        const cur = MH.top();
        const [curNode, curDist] = [cur.node, cur.dist];        
        MH.pop();
        
        if(curDist > Distance[curNode]) continue;
        for(const [nextNode, dist] of graph[curNode] ){
            const nextDist = curDist + dist;          
                 
            if(nextDist < Distance[nextNode]) {                
                Distance[nextNode] = nextDist;
                MH.push(nextNode, nextDist);
            }            
        }
    }
    for(const item of Distance) {
        if(item <= K)
            ret += 1;
    }
    return ret;
}

특이사항

    for(const [a,b,c] of road) {
        graph[a] = graph[a] || [];
        graph[b] = graph[b] || [];
        graph[a].push([b,c]);
        graph[b].push([a,c]);
    }

 값을 입력받을때 위와 같은 형식으로 입력받으면 최초로 값을 입력받을때 초기화를 간편하게 할 수 있다.