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

[ 문제 ]

 

• 문제 풀러 가기
• 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.

---

[출제 의도]

 

• 최단 경로 알고리즘

---

[ 문제 풀이 ]

 

먼저, 모든 노드에서 모든 노드로의 최단 경로를 구해야 합니다. Floyd-Warshal 알고리즘을 사용했습니다.

 

cost[i][j] = i에서 j로 가는 최저 택시 요금

 

 

그다음,  어느 노드를 A와 B의 분기점으로 정할지 구해야 합니다.

K를 분기점이라고 했을 때, S ~ K, K ~ A, K ~ B의 합이 최솟값일 때가 정답입니다.

 

문제에서 요구하는 답 = min(cost[s-1][k] + cost[k][a-1] + cost[k][b-1]) (단, k = 1 ~ n)

 

 

Dijkstra 알고리즘을 사용하지 않은 이유는 비효율적이기 때문입니다.

---

[ 정답 코드 ]

 

# n: 지점의 개수
# s: 출발 지점
# a: a의 도착 지점
# b: b의 도착 지점
# fares: 지점 사이의 예상 택시요금

from math import inf


def solution(n, s, a, b, fares):

    # 이동 최소 비용을 저장할 이차원 배열
    cost = [[inf] * n for _ in range(n)]
    for x, y, c in fares:
        cost[x-1][y-1] = c
        cost[y-1][x-1] = c

    # 플로이드 와샬 알고리즘
    for k in range(n):
        cost[k][k] = 0
        for i in range(n):
            for j in range(n):
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    # 합승 택시 요금 최솟값 탐색
    answer = inf
    for k in range(n):
        answer = min(answer, cost[s-1][k] + cost[k][a-1] + cost[k][b-1])

    return answer


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]]))