[JS] 합승 택시 요금

택시요금을 계산하는 다익스트라를 활용하는 문제이다.

 

 

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

프로그래머스

 

 

 

다익스트라 알고리즘을 활용하여 A를 넣으면 A에서 다른 곳으로 갈 수 있는 최소 거리를 얻어낼 수 있다.

 

만약 다익스트라에 4번 노드를 넣은 결과가 [1,2,3,4,0,6,7] 이 나왔다면 4번에서 5번으로 갈수 있는 최소거리는 6인 셈이다.

 

 

문제에서 제공한 그래프는 단방향이 아니라 양방향이다.

익스트라의 결과는 A -> 다른노드 로가는 최소거리이기도 하지만  다른노드 -> A 로 가는 최소거리이기도 하다.

 

따라서 S노드에서 다른노드로 가는 최소거리를 구한 이후, 각 노드를 순회하며 해당 노드에서 A,B로 가는 거리들을 합쳐가면서 그 최솟값을 구하면 꽤나 간단하게 구현할 수 있다.

 

 

 

 

 

function solution(n, s, a, b, fares) {
    const graph = [...Array(n+1)].map(_ => [])
    for (const [c,d,f] of fares){
        graph[c].push([d,f])
        graph[d].push([c,f])
    }
    
    const findMinDistNode = (map,visited) => {
        let ret = [0,Infinity]
        for (let i = 1 ; i<map.length ; i++ ){
            if (visited[i]) continue
            if (ret[1]>=map[i]) ret = [i,map[i]]
        }
        return ret[0]
    }
    
    const dijkstra = (startNode) => {
        const ret = Array(n+1).fill(Infinity)
        const visited = Array(n+1).fill(false)
        visited[startNode] = true
        ret[startNode] = 0
        for (const [end,dist] of graph[startNode]) ret[end] = Math.min(ret[end],dist)
        
        for (let i = 0 ; i < n-1 ;i++){
            const curNode = findMinDistNode(ret,visited)
            visited[curNode] = true
            for (const [end,dist] of graph[curNode]) {
                if(ret[end] > ret[curNode]+dist)
                    ret[end] = ret[curNode]+dist
            }
        }
        
        return ret
    }
    
    const sInfo = dijkstra(s)
    const aInfo = dijkstra(a)
    const bInfo = dijkstra(b)
    
    let ret = Infinity
    for (let node = 1 ; node <= n ; node ++ ){
        const cost = sInfo[node] + aInfo[node] + bInfo[node]
        if (ret > cost) ret = cost
    }
    
    return ret
    
}