[프로그래머스] 합승택시요금 (파이썬)

📕 문제

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

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

 

💡 풀이법

1. 노드들 중 어디까지 같이 가다가 서로 갈리는 길을 모르기 때문에 모든 노드에 대해 탐색한다.

2. 출발지부터 서로 갈리는 노드까지 dfs를 한번 돈다.

3. 서로 갈리는 노드에서 a가 도착하는 곳까지 dfs를 돌리고, 서로 갈리는 노드에서 b가 도착하는 곳까지 dfs를 돌린다.

from collections import defaultdict, deque

def taxi(n, s, e, graph):
    deq = deque([(s, 0)])
    dist = [float('inf') for _ in range(n+1)]
    dist[s] = 0

    while deq:
        x, d = deq.popleft()

        if dist[x] < d:
            continue

        for nx, nd in graph[x]:
            if dist[nx] > dist[x] + nd:
                dist[nx] = dist[x] + nd
                deq.append((nx, dist[nx]))

    return dist[e]


def solution(n, s, a, b, fares):
    graph = defaultdict(list)
    total = float('inf')

    for fare in fares:
        n1, n2, d = fare
        graph[n1].append((n2, d))
        graph[n2].append((n1, d))

    for i in range(1, n+1):
        share_fee = taxi(n, s, i, graph)
        a_fee = taxi(n, i, a, graph)
        b_fee = taxi(n, i, b, graph)
        total = min(total, share_fee + a_fee + b_fee)

    return total