[JS] 배달

문제부터 다익스트라 알고리즘을 공부해보란 의도가 보이는 문제였다.

 

 

다익스트라 알고리즘이란 그래프,간선이 주어질 때 최소의 경로를 찾아낼 수 있는 알고리즘의 한 종류이다.

 

 

 

1. 간선의 정보를 저장하는 graph배열 생성

2. 1번노드부터 다른노드까지의 길이를 저장할 dp배열 생성

3. 방문한 노드인지 아닌지에 대한 정보를 저장할 visited배열 생성

 

4. 방문하지 않은 노드들 중에서 최소거리에 있는 노드를 선택

5. grpah배열을 활용해서 각 노드들간의 거리를 최신화

6. 해당 노드는 방문한 노드로 변경

 

7. 4~6을 모든 노드를 반복할때까지 반복

 

이후 filter함수를 활용해서 K보다 작은 것들의 개수만 세주었다.

 

 

function solution(N, road, K) {
    const graph = new Array(N+1).fill(0).map(v => [])
    
    for (const [s,e,d] of road){
        graph[s].push([e,d])
        graph[e].push([s,d])
    }
    
    const dp = new Array(N+1).fill(Infinity)
    const visited = new Array(N+1).fill(false)
    
    dp[1] = 0
    
    const findSmallNode = () => {
        let ret = 1
        let tmp = Infinity
    
        for (let i = 1 ; i < dp.length ; i++){
            if (!visited[i] && dp[i] < tmp) {
                tmp = dp[i]
                ret = i
            }
        }
        return ret
    }
    
    
    for (let i = 1 ; i < dp.length ; i++) {
        const node = findSmallNode()
        visited[node] = true
        
        for (const [e,d] of graph[node]) {
            if (!visited[e] && dp[node]+d < dp[e]){
                dp[e] = dp[node]+d
            }
        }
    }
    
    return dp.filter(v=> v <= K).length
}