[프로그래머스] 합승 택시 요금 / 파이썬 / (플로이드 와샬)

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

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

풀이

2021 카카오 문제로 나온 플로이드 와샬 알고리즘을 통해 푸는 문제이다.
읽자마자 플로이드 와샬 문제임을 알아차렸고, 전형적인 문제라 딱히 풀이 설명이 존재하지 않는다.

def solution(n, s, a, b, fares):
    # 플로이드 와샬, 모든 정점으로부터의 최소 거리 구하고
    # ( 시작점 + x ) + ( x ~ A의 끝점) + (x ~ B의 끝점) 구해주면 될듯
    INF = 10987654321
    answer = INF

    # 초기화
    dist = [[ INF for _ in range(n+1)] for _ in range(n+1) ]
    for i in range(1, n+1):
        dist[i][i] = 0
    for (st, ed, w) in fares:
        dist[st][ed] = w
        dist[ed][st] = w

    # 플로이드 와샬
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # 답 구함
    for i in range(1, n+1):
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b])
    return answer