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

문제

• 무지와 어피치가 택시 합승을 적절히 이용해 택시요금을 얼마나 아낄 수 있을 지 계산하자
  • 무지와 어피치는 출발지점 s에서 각각 a와 b로 이동해야 한다.
  • 무지와 어피치 모두 집으로 귀가하는데 필요한 택시 요금의 최솟값을 찾아야 한다.
  • 3 <= 지점 n <= 200
  • 2 <= 간선 <= n(n-1) / 2

 

풀이

• 모든 경로를 확인한다고 가정하면, ... 시간 복잡도 계산이 잘 안돼서 우선 해봤다.
  • 시작 지점 s 에서 특정 지점 start 까지 함께 택시를 타고,
  • start 에서 a 까지 그리고 start 에서 b까지 각자 택시를 탄다고 생각하자.
  • cost = (s에서 start 까지 비용) + (start 에서 a까지 비용) + (start 에서 b까지 비용)

 

from collections import deque

def solution(n, s, a, b, fares):
    # graph[a][b] : a -> b 가는 최소 비용
    graph = [[1e9]*(n+1) for _ in range(n+1)] 
    for i in range(1, n+1):
        graph[i][i] = 0             # 자기 자신은 0으로 정의
        
    for start, end, cost in fares : # 간선 추가하기
        graph[start][end] = cost
        graph[end][start] = cost
    
    # 모든 지점에서 모든 지점까지의 최단 거리 찾기
    for k in range(1, n+1) :
        for start in range(1, n+1):
            for end in range(1, n+1) :
                graph[start][end] = min(graph[start][end], graph[start][k] + graph[k][end])
    
    # 최소 비용 찾기
    answer = 1e9
    for start in range(1, n+1) :
        cost = graph[s][start]      # s -> start 비용
        cost += graph[start][a]     # start -> a 비용
        cost += graph[start][b]     # start -> b 비용
        answer = min(answer, cost)
    
    return answer

 

References

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