[programmers/js] 합승 택시 요금

합승 택시 요금

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

문제 설명

"무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다. 이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.
만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

풀이

문제를 보면 최단거리문제임을 바로 알 수 있습니다.

주어진 문제는 출발지 s, 목적지 a, 𝑏간의 최소 이동 비용을 계산하는 문제입니다.
𝑠, a, b가 동일 경로를 공유할 수 있는 경우도 있으므로, 각 노드(1부터 n까지)를 경유지로 고려하여 비용을 계산해야 합니다.

우선 주어진 n개의 노드를 기반으로 n+1 크기의 그래프 인접 리스트를 생성합니다.
인덱스 0은 사용하지 않고, 1부터 n까지의 노드에 대해 [도착점, 거리]를 저장합니다.

다익스트라 알고리즘을 통해 s, a, b 3개 노드에서의 최단 거리만 구해줍니다.

이유는 s->1->3->a가 최단 거리일 때, s -> 1 + 1 -> a 또는 s -> 2 + 2 -> a의 거리는 같기에 3개 노드의 최단 거리를 구해도 답을 찾을 수 있습니다.

function solution(n, s, a, b, fares) {
    // 최단거리 문제 -> 다익스트라 (우선순위 큐 활용)
    const graph = Array.from({ length: n + 1 }, () => []);

    // 그래프 연결
    for (const [start, end, cost] of fares) {
        graph[start].push([end, cost]);
        graph[end].push([start, cost]);
    }

    // 다익스트라 알고리즘 (우선순위 큐 사용)
    const dijkstra = (start) => {
        const dist = Array(n + 1).fill(Infinity);
        const pq = [[0, start]]; // [거리, 노드]
        dist[start] = 0;

        while (pq.length) {
            pq.sort((a, b) => b[0] - a[0]); // 오름차순 정렬
            const [currentDist, currentNode] = pq.pop();

            if (currentDist > dist[currentNode]) continue;

            for (const [nextNode, cost] of graph[currentNode]) {
                const newDist = currentDist + cost;
                if (newDist < dist[nextNode]) {
                    dist[nextNode] = newDist;
                    pq.push([newDist, nextNode]);
                }
            }
        }

        return dist;
    };

    // 각각의 다익스트라 실행
    const sDist = dijkstra(s);
    const aDist = dijkstra(a);
    const bDist = dijkstra(b);

    // 최소 비용 계산
    let minCost = Infinity;
    for (let node = 1; node <= n; node++) {
        const totalCost = sDist[node] + aDist[node] + bDist[node];
        minCost = Math.min(minCost, totalCost);
    }

    return minCost;
}