programmers Level 3 합승 택시 요금

문제

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

걸린 시간

00 : 00 : 19

풀이

JavaScript

function solution(n, s, a, b, fares) {
    // n 차원 배열 생성 함수
    const n_array = (li, i, n, el) => {
        if(i === li.length-1){
            if(typeof el === 'object'){
                const tmp = Array(li[i]);
                for(let i = 0; i < li[i]; i++)
                    tmp[i] = JSON.parse(JSON.stringify(el))
                return tmp;
            }
            else return Array(li[i]).fill(el);
        }
        else return Array.from(Array(li[i]), () => n_array(li, i+1, n, el))
    }
    // 인접배열 생성
    const adj = n_array([n+1, n+1], 0, 2, Number.POSITIVE_INFINITY);
    for(let fa of fares){
        let c = fa[0];
        let d = fa[1];
        let f = fa[2];
        adj[c][d] = f;
        adj[d][c] = f;
    }
    // 플로이드 와샬
    for(let i = 1; i < n+1; i++)
        adj[i][i] = 0;
    for(let k = 1; k < n+1; k++)
        for(let i = 1; i < n+1; i++)
            for(let j = 0; j < n+1; j++)
                adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
    let ans = Number.POSITIVE_INFINITY;
    for(let m = 1; m < n+1; m++){
        if(adj[s][m] === Number.POSITIVE_INFINITY) continue;
        if(adj[m][a] === Number.POSITIVE_INFINITY) continue;
        if(adj[m][b] === Number.POSITIVE_INFINITY) continue;
        ans = Math.min(ans, adj[s][m] + adj[m][a] + adj[m][b]);
    }
    return ans;
}

정점의 개수 n 이 200 으로 매우 작기 때문에 플로이드 와샬 알고리즘을 통해 n^3 으로 정점 간 최단 경로를 모두 구할 수 있다.

모든 정점을 중간 지점으로 하여 합승한 후 각자 집으로 돌아가는 모든 경우를 조사해주면 된다.