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

문제 설명

좌표의 개수와 각 좌표 간의 거리를 입력받고 한 점 s에서 두 점 a, b로 각각 이동하는 이동 거리의 합의 최솟값을 구하는 문제입니다. 단 a, b로 이동하기 전에 함께 한 점으로 이동한 뒤 이동한 점에서부터 각각 이동할 수도 있는데 이때는 한 점으로 이동할 때의 이동 거리는 두 번 계산하지 않고 한 번만 계산합니다.

작동 순서

1. 각 점들간의 이동 거리를 저장할 배열을 생성합니다.
2. 각 점들간의 이동 거리를 입력받습니다.
3. 플로이드 워셜 알고리즘을 통해서 각 점들간의 최소 이동 거리를 구합니다.
4. 시작점에서 어느 한점까지 이동한 거리와 그 점에서부터 각각 이동한 거리를 합한 값을 구하고 그 중 최솟값을 출력합니다.

소스코드

def solution(n, s, a, b, fares):
    answer = 1e9
    dp=[[1e9 for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(1, n+1):
        dp[i][i]=0
        
    for fare in fares:
        dp[fare[0]][fare[1]]=fare[2]
        dp[fare[1]][fare[0]]=fare[2]
        
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if dp[i][j]>dp[i][k]+dp[k][j]:
                    dp[i][j]=dp[i][k]+dp[k][j]

    for i in range(1, n+1):
        total=dp[s][i]
        total+=dp[i][a]
        total+=dp[i][b]
        answer=min(answer, total)
    return answer