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

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

POINT

최소 비용 (s -> i) + (i -> a) + (i -> b)

예제에서 4 → 1 → 5, 5 → 6 , 5 → 3 → 2 처럼, 어피치와 무지는 특정 노드(i=5)를 기준으로 이동한다. 둘이 합승하지 않는 경우는 i=s일 때이다.

플로이드 워셜(Floyd-warshall) 알고리즘

그래프를 활용한 최단 거리(최소 비용) 문제이므로, 다익스트라(Dijkstra데이크스트라)나 플로이드 워셜을 사용하여 푼다. 노드 개수(n)가 200이하로 연산이 많지 않고, 특정 구간(i)을 지나가므로, 구현이 간단한 플로이드 워셜로 풀었다. 이 알고리즘은 모든 노드 a, b에 대하여, a에서 b로 가는 모든 최단 거리를 graph에 저장한다.

풀이

INF = int(1e9)

def solution(n, s, a, b, fares):
    # 그래프 생성 - 간선 정보 저장
    graph = [[INF] * (n+1) for _ in range(n+1)]
    for i, j, k in fares:
        graph[i][j] = k
        graph[j][i] = k
    
    # floyd-warshall 알고리즘 수행
    for k in range(n+1):
        for i in range(n+1):
            for j in range(n+1):
                # 자기 자신으로 가는 비용은 0
                if i == j: graph[i][j] = 0
                else:
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
                    
    # 최소 비용 구하기
    answer = graph[s][1] + graph[1][a] + graph[1][b]
    for i in range(2, n+1):
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b])
        
    return answer