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

https://school.programmers.co.kr/learn/courses/30/lessons/72413

🤔 문제분석

주어진 문제를 풀기위해서는 플로이드 워셜을 알고 있어야한다.

1. 임의의 노드로부터 각 임의의 노드까지 모든 최단경로를 구한다.
2. s로 부터 임의의 노드를 들려서(a와 b가 같이 택시를 탐) 각 a, b 노드까지 가는 거리중 최소값을 고르면 된다.

물론, n이 300이기 때문에 플로이드 워셜로 접근해도 되지만 만약 n이 더 커질경우 $n^3$ 시간복잡도가 크게 증가 할 수 있다. n이 충분히 커진다면 데이크스트라를 고려하는것도 하나의 방법이 될 수 있겠다.

💻 코드

import sys

def solution(n, s, a, b, fares):
    distance = [[sys.maxsize] * (n+1) for _ in range(n+1)]

    for i in range(1, n+1):
        distance[i][i] = 0

    for c, d, f in fares:
        distance[c][d] = f
        distance[d][c] = f

    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                distance[i][j] = min(distance[i][k]+distance[k][j], distance[i][j])

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

    return answer