합승 택시 요금 (72413번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 합동 택시 요금 (72413번)

 

난이도 : Lv 3

알고리즘 : Dijkstra (다익스트라)

풀이 소요 시간 : 30 mins

 

 

import sys
from heapq import heappop, heappush


def solution(n, s, a, b, fares):
    def dijkstra(x, d):
        pq = [(0, x)]
        while pq:
            nd, nn = heappop(pq)
            if d[nn] < nd:
                continue
            d[nn] = nd
            for cd, cn in graph[nn]:
                if d[cn] <= nd+cd:
                    continue
                heappush(pq, (nd+cd, cn))
        return d
    
    
    INF = sys.maxsize
    graph = [[] for _ in range(n+1)]
    for x, y, d in fares:
        graph[x].append((d, y))
        graph[y].append((d, x))
    aa = [INF] * (n+1)
    bb = [INF] * (n+1)
    ss = [INF] * (n+1)
    aa[a] = bb[b] = ss[s] = 0
    aa = dijkstra(a, aa)
    bb = dijkstra(b, bb)
    ss = dijkstra(s, ss)
    return min(ss[i] + aa[i] + bb[i] for i in range(1, n+1))

 

 

전형적인 다익스트라 문제이다.

 

---

 

 

① 다익스트라를 활용해서,

S, A, B 세 군데 지점에서 각각 다른 지점까지의 최단거리를 구한다.

 

이를

ss, aa, bb

리스트에 저장했다.

 

 

 

② for 문을 활용해서 1번부터 n번 지점까지

ss[i] + aa[i] + bb[i]

중 최솟값을 구한다.

min( ss[i] + aa[i] + bb[i] for i in range(1, n+1) )

그 값이 "최소" 합승 택시 요금이다.