[Python] 프로그래머스 level3 합승 택시 요금

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

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

🍟 풀이 방법 

• 다익스트라를 이용해 최단 경로를 찾는다. 다익스트라에 대한 설명은 아래 포스팅을 참고
• s에서 i까지 이동하는 최단 경로 + i에서 a이동 최단경로 + i에서 b이동 최단경로 → 이 값이 최소가 되는 i를 찾기

최단 경로 찾기 알고리즘 (다익스트라, 벨만포드, 플로이드 워셜), 관련 백준 문제 파이썬 풀이

 

🍔 전체 코드

# 합승 택시 요금
import heapq
def dijkstra(start, n):
    dist = [float('inf')]*(n+1)
    dist[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))
    while queue:
        cost, temp = heapq.heappop(queue)
        if dist[temp] < cost: continue
        for i in range(1, n+1):
            if dist[i] > graph[temp][i] + cost:
                dist[i] = graph[temp][i] + cost
                heapq.heappush(queue, (dist[i], i))
    return dist

graph = [[float('inf')]*(201) for _ in range(201)]
def solution(n, s, a, b, fares):
    answer = float('inf')
    for x, y, c in fares:
        graph[x][y] = c
        graph[y][x] = c
    distance = dijkstra(s, n)
    for i in range(1, n+1):
        temp = dijkstra(i, n)
        answer = min(temp[a]+temp[b]+distance[i], answer)
    return answer
    
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]])