[프로그래머스] 배달 (JavaScript)

프로그래머스 배달

문제풀이

자바스크립트로 다익스트라를 구현해보았다.

• 2차원 배열 만들기 (인접리스트로 사용)
  • Array.from(Array(length), () => new Array());
• 우선순위 큐 만들기

  • class PriorityQueue {
      constructor() {
          this.memory = [];
          this.length = 0;
      }
      push(newItem) {
          this.length++;
          let isAdded = false;
          for(let i = 0 ; i < this.memory.length ; ++i){
              if(this.memory[i].weight > newItem.weight){
                  this.memory.splice(i, 0, newItem);
                  isAdded = true;
                  break;
              } 
          }        
          if(!isAdded) this.memory.push(newItem);
      }
      pop() {
          this.length--;
          return this.memory.shift();
      }
    }

  • 거리로 오름차순 정렬되도록 만들었다.
• 즉시실행함수를 사용했다.

구현코드

function solution(N, road, K) {
    const pq = new PriorityQueue();
    const adj = Array.from(Array(N + 1), () => new Array());
    const dist = [0, 0];

    for(let i = 0 ; i < N - 1 ; ++i) dist.push(Number.MAX_VALUE);
    
    road.map(info => {
        let a = info[0];
        let b = info[1];
        let c = info[2];
        
        adj[a].push({to: b, weight: c});
        adj[b].push({to: a, weight: c});
    });
    
    pq.push({
        to: 1,
        weight: 0
    });
    
    (function(){
        while(pq.length){
            let edge = pq.pop();
            adj[edge.to].map(next => {
               if(dist[next.to] > dist[edge.to] + next.weight){
                   dist[next.to] = dist[edge.to] + next.weight;
                   pq.push(next);
               } 
            });
        }
    })();
        
    let answer = 0;
    for(let i = 1 ; i < N + 1 ; ++i){
        if(dist[i] <= K) answer++;
    }
    
    return answer;
}

class PriorityQueue {
    constructor() {
        this.memory = [];
        this.length = 0;
    }
    
    push(newItem) {
        this.length++;
        
        let isAdded = false;
        
        for(let i = 0 ; i < this.memory.length ; ++i){
            if(this.memory[i].weight > newItem.weight){
                this.memory.splice(i, 0, newItem);
                isAdded = true;
                break;
            } 
        }        
        
        if(!isAdded) this.memory.push(newItem);
    }
    
    pop() {
        this.length--;
        return this.memory.shift();
    }

}