[Programmers] Python 합승 택시 요금 (72413)

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

프로그래머스

 

다익스트라 응용 문제이다.

1. a, b 각각 가는 비용을 다익스트라로 구한다.

2. a, b 각각 구한 비용을 중심으로 비교할 대상을 반복을 돌며, 

(s -> i 의 동행 거리) + (i -> a 거리) + (i -> b 거리) 가 최소가 되는 것을 찾으면 된다.

 

import heapq
def solution(n, s, a, b, fares):
    answer = 0
    graph=[[] for _ in range(n+1)]
    for start, end, cost in fares:
        graph[start].append((end,cost))
        graph[end].append((start, cost))

    def dijkstra(start):
        hq = []
        distance = [float('inf')] * (n+1)

        distance[start] = 0
        heapq.heappush(hq,(0,start))

        while hq:
            dist, now_node = heapq.heappop(hq)

            for next_node, cost in graph[now_node]:
                if distance[next_node] > dist+cost:
                    distance[next_node] = dist + cost
                    heapq.heappush(hq,(dist+cost, next_node))

        return distance

    origin_distance = dijkstra(s)
    result = origin_distance[a] + origin_distance[b]

    for i in range(n+1):
        if i == s:
            continue
        else:
            ab_distance=dijkstra(i)
            result = min(result, origin_distance[i] + ab_distance[a] + ab_distance[b])

    return result


print(solution(6,4,6,2,	[[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]]))

 

회고.

다익스트라를 부분적으로 잘라서 하는 문제를 풀어봤으나 이런식으로 나누는 것을 새로운 느낌이였다. 도움이 많이 된 문제였다.