(Python) 프로그래머스 - 합승 택시 요금

09 Mar 2022 in Algorithm on Programmers, Level3

[문제 링크]

def solution(n, s, a, b, fares):
    INF = int(1e9)
    graph = init_graph(fares, n, INF)

    answer = INF
    for share_spot in range(1, n + 1):
        if graph[s][share_spot] != INF:
            answer = min(answer, graph[s][share_spot] + graph[share_spot][a] + graph[share_spot][b])

    return answer


def init_graph(fares, n, INF):
    graph = [[INF] * (n + 1) for _ in range(n + 1)]

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

    for x, y, cost in fares:
        graph[x][y] = cost
        graph[y][x] = cost

    for k in range(1, n + 1):
        for x in range(1, n + 1):
            for y in range(1, n + 1):
                graph[x][y] = min(graph[x][k] + graph[k][y], graph[x][y])
    return graph

간단한 플로이드 워셜 문제다.