programmers. 합승 택시 요금

문제

문제

코딩테스트 연습 - 합승 택시 요금

틀린 풀이

택시를 같이 타고 가는 지점을 중간점 이라고 했을 때 합승 택시 요금의 최소값은

시작점->중간점 + 중간점->A도착점 + 중간점->B도착점 이 최소가 될 때이다

시작점을 기준으로 모든 정점의 최소값을 구할 수 있는 다익스트라 알고리즘을 사용해서 시작점에서 모든 정점의 최소값을 한 번 구하고 (이 때 구해지는 값은 시작점->중간점)

정점 개수만큼 다익스트라를 사용하여 각 정점에서의 최소값을 다시 구한다 이 때 자기 자신의 값은 0으로 처리를 해주어야 값이 중복처리되지 않는다

코드

    function solution(n, s, a, b, fares) {
        var answer = Infinity;
        const adj = Array(n).fill().map(()=> []);
        const path = Array(n).fill([]);

        fares.forEach(v=>{
            const [from, to, value] = v;
            adj[from-1].push([to-1,value]);
            adj[to-1].push([from-1,value]);
        });
        const mid = dijkstra(s);

        for(let i=1;i<=n;i++){
            const arr = dijkstra(i);
            const [distA, distB] = [arr[a-1],arr[b-1]];

            console.log(`중간점이 ${i} 일 때`);
            console.log(`mid : ${mid[i-1]} A: ${distA} B: ${distB}`);

            answer = Math.min(answer, mid[i-1] + distA + distB);
        }


        function dijkstra(start)  {
            const arr = [[start-1,0]];
            const dist = Array(n).fill(Infinity);

            repeat(arr,dist);
            console.log(`${start}, start`);
            console.log(dist);

            dist[start-1]=0;
            return dist;
        }

        console.log(answer)

        function repeat(arr,dist){
            while (arr.length){
                const [node, value] = arr.shift();

                adj[node].forEach(([edge,weight])=>{
                    if(dist[edge]> value+weight) {
                        dist[edge] = value+weight;
                        path[edge];
                        arr.push([edge, dist[edge]]);
                    }
                });
            }
        }

        return answer;
    }

이 방법으로는 효율성 테스트에서 시간 초과가 발생하여 풀지 못했다

풀이

플로이드 와샬 알고리즘으로 풀면 각각의 정점까지의 최소 비용을 한 번만 구해놓으면 되기 때문에 효율성 테스트도 통과할 수 있다

코드

    function solution(n, s, a, b, fares) {
        let answer = Infinity;
        const adj = Array(n).fill().map(() => Array(n).fill(Infinity));

        fares.forEach(v => {
            adj[v[0] - 1][v[1] - 1] = v[2];
            adj[v[1] - 1][v[0] - 1] = v[2];
            adj[v[1] - 1][v[0] - 1] = v[2];
        });
        console.log(JSON.parse(JSON.stringify(adj)))

        for(let mid=0;mid<n;mid++){
            for(let i=0;i<n;i++){
                for(let j=0;j<n;j++){
                    if(adj[i][j] > adj[i][mid]+ adj[j][mid]) {
                        adj[i][j] = adj[i][mid]+ adj[j][mid];
                    }
                }
            }
        }

        for(let i=0; i<n;i++){
            adj[i][i] = 0;
        }

        for(let i=0;i<n;i++){
            answer = Math.min(answer, adj[s-1][i] + adj[i][a-1] + adj[i][b-1]);

        }
        return answer
    }