[프로그래머스] 합승 택시 요금 - PYTHON

문제 주소 : https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

특정 노드부터 S, A, B까지 최소 금액을  s, a, b라고 했을 때 s+a+b의 최솟값을 구하는 것이 이 문제의 목표다.

따라서 S, A, B과 다른 노드들의 최소 금액을 모두 구했다. 사용한 알고리즘은 dijkstra인데, dijkstra 알고리즘에 대한 자세한 풀이는 다른 블로그를 참조바란다!

 

import math

def dijkstra(now, n, fares):
    check = [0 for _ in range(n+1)]
    dist = [math.inf for _ in range(n+1)]
    dist[now] = 0
    for _ in range(n):
        edges = [edge for edge in fares if edge[0] == now or edge[1] == now]
        for edge in edges:
            next = edge[0] if edge[0] != now else edge[1]
            if check[next] == 1:
                continue
            fare = edge[2] + dist[now] 
            dist[next] = fare if dist[next] > fare else dist[next]

        check[now] = 1
        arr = [d if check[i] == 0 else math.inf for i, d in enumerate(dist) ]
        now = arr.index(min(arr))

    return dist

def solution(n, s, a, b, fares):
    answer = []
    s_dij = dijkstra(s, n, fares)
    a_dij = dijkstra(a, n, fares)
    b_dij = dijkstra(b, n, fares)

    for i, node in enumerate(s_dij):
        if node == math.inf:
            continue
        answer.append(node + a_dij[i] + b_dij[i])

    return min(answer)