[Python Algorithm] 프로그래머스 합승 택시 요금 - Taxi Fare

Chani·2022년 3월 9일
0

알고리즘

목록 보기
10/16
post-thumbnail

풀이 과정

S 지점에서 A,B 지점까지 도착하는데 소요되는 최소 비용을 구하는 문제이다.
처음에는 문제를 대충읽고 S->A->B로 가는 비용과 S->B->A로 가는 비용만 비교하면 되는줄 알았는데, 그게 아니라 S에서 출발해서 따로 따로 A, B로 가는데 경로가 중복되는 부분이 있다면 함께 갈 수 있으므로 비용이 한번만 계산되어야 하는... 그런 문제였다.

다익스트라 알고리즘을 사용하여 문제를 해결하려면 비용뿐 아니라 도착 지점까지의 경로도 함께 저장을 해주어야 중복되는 경로가 있을때 비용을 정확히 계산을 해줄수 있다.

이렇게 풀어주려고 하니 오히려 더 문제를 복잡하게 푸는것 같아 플로이드-워셜 알고리즘을 이용해 문제를 해결하였다.
먼저 모든 경로에 대해 최소비용을 구해주고, (S->C) + (C->A) + (C->B)로 가는 비용을 더해주는 방식으로 구현하였다. (단, C는 A와B가 합승한 이후 하차하는 지점)

C가 어느 지점인지 모르기 때문에 1~n 까지 순회하면서 최소값을 찾아주는 방식으로 답을 찾아주었다.


최종 코드

INF = float('INF')
def solution(n, s, a, b, fares):
    distance = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    
    for i in fares:
        distance[i[0]][i[1]] = i[2]
        distance[i[1]][i[0]] = i[2]
    
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i == j:
                    distance[i][j] = 0
                elif distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]
    answer = INF
    for i in range(1, n + 1):
        answer = min(answer, distance[s][i] + distance[i][a] + distance[i][b])
    return answer

결과


합승 택시 요금 문제 출처
GitHub 코드

profile
프론트엔드에 스며드는 중 🌊

0개의 댓글