[프로그래머스] 합승 택시 요금 / Python / 2021 KAKAO BLIND RECRUITMENT

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

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

---

---

Solution

import heapq
INF = int(1e9)

def dijkstra(distance, start, graph):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, curr = heapq.heappop(q)
        if distance[curr] < dist:
            continue
        for i in graph[curr]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

def solution(n, s, a, b, fares):
    graph = [[] for _ in range(n+1)]
    for fare in fares:
        x, y, z = fare
        graph[x].append((y, z))
        graph[y].append((x, z))
    
    distance = [INF] * (n+1)
    dijkstra(distance, s, graph)
    ans = INF
    for i in range(1, n+1):
        result = 0
        distance_tmp = [INF] * (n+1)
        dijkstra(distance_tmp, i, graph)
        result = distance[i] + distance_tmp[a] + distance_tmp[b]
        ans = min(ans, result)
    return ans

 

다익스트라를 사용하는 문제였다.

먼저, 출발 지점인 s에 대해서 모든 경로에 대해 최단 거리를 구한다. 그리고 1번지점 부터 모든 지점에 대하여 최단 거리를 구한 후 s에서 i번까지의 거리, 그리고 i에서 a까지 가는 거리와 i에서 b까지 가는 거리를 더한 값 중에 가장 작은 값을 구하면 된다. 즉 i는 환승 지점이 되는 것이다. 말로하니까 굉장히 헷갈린다.

 

택시 요금 = distance[i](s에서 환승 지점으로의 요금) + distance_tmp[a](환승 지점에서 a까지의 요금) + distance_tmp[b](환승 지점에서 b까지의 요금)