[프로그래머스]환승 택시 요금 - 카카오 2021(Python)

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

문제요약
그래프 상에서 어피치와 무지가 어느 지점까지 같이 택시를 타고, 그 지점에서 각자의 집을 갈때 비용이 최소가 되는 환승 지점구해서 비용 구해야 됨.

1. 플로이드-와샬 알고리즘으로 모든 노드에서 모든 노드로 가는 최소 비용 구함
2. 1~n 지점 중에 (시작구간~k지점) + (k지점~무지 집) + (k지점~어피치집)이 최소가 되는 지점과 비용 구함

def solution(n, s, a, b, fares):
    answer = 1e9
    # 초기화
    taxi = [[1e9] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        taxi[i][i] = 0
    
    # 인접행렬에 비용 저장 - 양쪽 왔다갔다 가능이므로 양방향 
    for i in range(len(fares)):
        city1, city2, money = fares[i]
        taxi[city1][city2] = money
        taxi[city2][city1] = money
        
    # 플로이드 와샬
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                taxi[i][j] = min(taxi[i][j], taxi[i][k] + taxi[k][j])
    
    # i는 환승지점. 어느지점에서 환승하면 비용이 최소가 되는지
    for i in range(1, n + 1):
        answer = min(answer, taxi[s][i] + taxi[i][a] + taxi[i][b])
    return answer