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

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

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

 

저번에 풀었던 '배달' 문제랑 비슷하다. 다익스트라 알고리즘을 이용하여 

(s, 도작지) + (도착지, a) + (도착지, b) 의 최솟값을 찾으면 된다. (여기서, (x, y) = (y, x))

 

출발지점 s 에서 a 와 b 로 가는 경로가 존재하는 경우만 주어지지만 입출력 예제 2번을 보면 분리된 장소도 있으므로 m 이 0 보다 큰 것 중 최솟값을 반환하면 된다.

 

from collections import defaultdict, deque

def solution(n, s, a, b, fares):
    answer = float('inf')
    dic = defaultdict(list)
    
    for i in fares:
        x, y, z = i
        dic[x].append([y, z])
        dic[y].append([x, z])
    
    AB = dijkstra(s, dic)
    A = dijkstra(a, dic)
    B = dijkstra(b, dic)
    
    for i in range(1, n+1):
        m = AB[i] + A[i] + B[i]
        if answer > m and m != 0:
            answer = m

    return answer

def dijkstra(start, dic):
    queue = deque([start])
    fee = defaultdict(int)
    
    while queue:
        x = queue.popleft()
        
        for y, z in dic[x]: 
            if y != start and (fee[y] > fee[x] + z or fee[y] == 0):
                fee[y] = fee[x] + z
                queue.append(y)

    return fee
  
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]])) # 82