〔프로그래머스/파이썬〕합승 택시 요금(Floyd-Warshall)

출처

프로그래머스

 

---

 

풀이

def solution(n, s, a, b, fares):
    answer = 0
    INF = n * 100000 + 1
    # 모든 노드 무한으로 초기화
    cost = [[INF] * n for _ in range(n)]
    # 자기자신->자기자신 비용 0원
    for i in range(n):
        cost[i][i] = 0
    # 인접한 노드들간의 비용 적용
    for fare in fares:
        start = fare[0] - 1
        finish = fare[1] - 1
        price = fare[2]
        cost[start][finish] = price
        cost[finish][start] = price
    # 플로이드와샬
    for m in range(n): # 경유지
        for i in range(n): # 시작점
            for j in range(n): # 종료점
                cost[i][j] = min(cost[i][j], cost[i][m] + cost[m][j])
    # 어느 경유지를 지나야 최소 비용인지 계산
    answer = INF
    for m in range(n):
        answer = min(answer, cost[s-1][m] + cost[m][a-1] + cost[m][b-1])
    return answer

 

---

 

노트

• 플로이드-와샬 문제를 풀어보고 싶어서 찾은 카카오 코테 문제
• 처음에는 3중 루프를 통해 모든 정점간의 최단비용을 구하는 플로이드 와샬 알고리즘 까지는 이해 되었는데, 마지막에 왜 그냥 cost[s-1][a-1] + cost[s-1][b-1] 하면 안 되고 다시 한 번 n번의 루프를 돌려서 최소 비용을 구하는지 이해가 안 됐었다
• 이는 문제에서 A, B 두 사람의 합승하는 경우까지 고려해야 했기 때문에 어느 경유지까지 함께 타고 갈려야 최소 비용인지까지 판단하기 위해서였다