[코딩테스트] 프로그래머스 javascript 2단계 - 배달 , 다익스트라

배달

- 이 문제는 다익스트라 즉 최단거리를 찾는 문제이다. 

- 한 노드에서 모든 노드를 검색하는 문제를 다익스트라라고 말한다.

 

각각의 노드를 방문했을 때 출발지에서 현재 노드까지 가장 가까운 시간만을 저장하면 된다. 

 

문제 풀이

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

프로그래머스

문제 설명

1. 처음에 노드를 기준으로 총 시간과 이동방향 모두를 저장할 배열을 생성한다.

- 이때, N+1 즉 노드의 개수 보다 하나 더 추가하여 구현을 쉽게 한다. 

 

2. queue를 생성해서 현재 total보다 노드를 방문하는 게 더 시간이 적을 때, queue에 넣고 total을 갱신한다.

 

전체 코드는 다음과 같다. 

function solution(N, road, K) {
    //1. 총 시간과 방향 배열 저장
    const total = new Array(N+1).fill(Infinity)
    const dir = Array.from({length:N+1},() => [])
    total[1] = 0
    road.forEach(([s,e,t])=>{
        dir[s].push({to:e,time:t})
        dir[e].push({to:s,time:t})
    })
    // console.log(road)
    
    // 2. queue 생성 
    let queue = [{to:1,time:0}]
    while(queue.length){
        const {to,time} = queue.shift()
        dir[to].forEach((step)=>{
            if(total[step.to]>total[to]+step.time){
                total[step.to] = total[to]+step.time
                queue.push(step)
            }
        })
    }
    return total.filter(v=>v<=K).length
}