문제 링크

프로그래머스 문제

풀이

전통적인 그래프 문제라고 볼 수 있을것 같다.
중요한 점은 시작지점과 종료 지점이 정해져 있으며,
그 사이에 중점만 변경시켜 가면서 가장 적은 값을 찾아내면 되기 때문에,
graph 간선을 모두 만들어주고, start, end를 기준으로 모든 경로를 찾아준다.

코드

function solution(n, s, a, b, fares) {
    var answer = Infinity;
    
    let graph = new Array(n+1).fill().map(() => new Array(n+1).fill(Infinity))
    
    fares.map(v => {
        const [start , end, cost] = v
        graph[start][end] = cost
        graph[end][start] = cost
        graph[start][start] = 0
        graph[end][end] = 0
    })
    
    
    for(let mid = 1; mid <=n; mid++){
        for(let start = 1; start<=n; start++){
            for(let end = 1; end <=n; end++){
                    graph[start][end] = Math.min( graph[start][end], graph[start][mid] + graph[mid][end])
            }
        }
    }
    
    for(let mid = 1; mid <=n; mid++){
        answer = Math.min(answer , graph[s][mid] + graph[mid][a]+ graph[mid][b])
    }
    
    
    return answer;
}