[카카오 2021] 합승 택시 요금

문제분석

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

즉, 출발 지점. A 도착 지점. B 도착 지점이 주어진다.
중간 지점까지 합승이 가능할 때 A와 B가 목적지까지 가기 위한 최단경로 찾기.

아이디어

효율성이 있는 문제이므로 heapq 활용한 다익스트라 사용
합승 내리는 노드 찾는게 관건.
합승 내리는 노드는 결국 출발지점, A도착지점, B도착지점 세 노드까지 거리의 합이 최소가 되는 노드가 되며. 그 거리가 답이 된다.
출발지점, A도착지점, B도착지점에서 각각 다익스트라 수행하고. 1~n까지 노드 중 세 다익스트라 결과 배열값의 합이 최소가 되는 노드 찾자.

코드

import heapq

def dijkstra(start, n, graph):
    q = []
    INF = int(1e9)
    distance = [INF] * (n + 1)
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n+1)]
    for q, w, dist in fares:
        graph[q].append((w, dist))
        graph[w].append((q, dist))
    distance1 = dijkstra(s, n, graph) #출발지점에서 모든노드까지 최소거리
    distance2 = dijkstra(a, n, graph) #A도착지점에서 
    distance3 = dijkstra(b, n, graph) #B도착지점에서
    
    result = int(1e9)
    for i in range(1, n+1):
        #temp : 각 노드에서 s, a, b로의 최소거리의 합. 즉 합승 고려한 최단경로
        temp = distance1[i] + distance2[i] + distance3[i]
        result = min(temp, result) 
    
    return result