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

출처 : programmers.co.kr/learn/courses/30/lessons/72413

 

알고리즘 분류 : 다익스트라 (with Python)

---

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다.

 

(중략)

 

 

(중략)

• 예상되는 최저 택시요금은 다음과 같이 계산됩니다.
  • 4→1→5 : A, B가 합승하여 택시를 이용합니다. 예상 택시요금은 10 + 24 = 34원 입니다.
  • 5→6 : A가 혼자 택시를 이용합니다. 예상 택시요금은 2원 입니다.
  • 5→3→2 : B가 혼자 택시를 이용합니다. 예상 택시요금은 24 + 22 = 46원 입니다.
  • A, B 모두 귀가 완료까지 예상되는 최저 택시요금은 34 + 2 + 46 = 82원 입니다.

 

 

문제

 

지점의 개수 n, 출발지점을 나타내는 s, A의 도착지점을 나타내는 a, B의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares가 매개변수로 주어집니다.

 

이때, A, B 두 사람이 s에서 출발해서 각각의 도착 지점까지 택시를 타고 간다고 가정할 때, 최저 예상 택시요금을 계산해서 return 하도록 solution 함수를 완성해 주세요.

 

만약, 아예 합승을 하지 않고 각자 이동하는 경우의 예상 택시요금이 더 낮다면, 합승을 하지 않아도 됩니다.

 

 

 

입출력 예

 

n	s	a	b	fares	result
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
7	3	4	1	[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]]	14
6	4	5	6	[[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4,8], [4,3,9]]	18

 

입출력 설명

 

(생략)

---

접근

• java로 DFS, BFS를 활용한 경험은 있으나, python으로 하려다보니 버벅인 부분이 많았다.
• 덕분에 다익스트라 알고리즘을 복기하는 계기가 되었다.

---

코드

import heapq
from math import inf


def dijkstra(n, graph, start) : 
    dist = [inf for _ in range(n)]
    dist[start] = 0

    queue = []

    heapq.heappush(queue, [dist[start], start])

    while queue : 
        cur_distance, now_position = heapq.heappop(queue)
        if dist[now_position] >= cur_distance : 
            for i in range(n) : 
                new_distance = cur_distance + graph[now_position][i]
                if new_distance < dist[i] : 
                    dist[i] = new_distance
                    heapq.heappush(queue, [new_distance, i])
    
    return dist

def solution(n, s, a, b, fares) : 
    answer = inf
    s, a, b = s-1, a-1, b-1
    graph = [[inf]*n for _ in range(n)]
    for u, v, w in fares : 
        graph[u-1][v-1] = graph[v-1][u-1] = w

    min_graph = []
    
    for i in range(n) : 
        min_graph.append(dijkstra(n, graph, i))

    for k in range(n):
        answer = min(answer, min_graph[s][k] + min_graph[k][a] + min_graph[k][b])

    return answer