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

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

최단거리를 찾는 문제이다.
최단거리가 나오면 항상 다익스트라, 플로이드 워셜 알고리즘을 생각해야 한다고 배웠었다.

처음에는 플로이드 워셜 알고리즘을 사용해 문제를 해결하려 했다가 시작점에서 bfs를 돌리면서 워셜 알고리즘을 사용해서 시간 초과가 났다...
지금 생각해보면 최단거리를 다 구했으니, 시작점에서 어느지점까지 같이 택시를 타고 갈지만 정하면 되기 때문에, 각 정점마다 같이 타고 간다고 생각하여 모든 경우의 수를 그냥 찾아주면 되었다...
물론 다익스트라를 사용해서도 문제를 풀 수 있다.

• 다익스트라 풀이

import math
import heapq
def dijkstra(graph, start):
    distance = [math.inf] * (len(graph) + 1)
    distance[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])
    while heap:
        cost, src = heapq.heappop(heap)
        for c, n in graph[src]:
            c += cost
            if c < distance[n]:
                distance[n] = c
                heapq.heappush(heap, [c, n])
    return distance


def solution(n, s, a, b, fares):
    graph = [[] for i in range(n + 1)]
    for fare in fares:
        graph[fare[0]].append([fare[2], fare[1]])
        graph[fare[1]].append([fare[2], fare[0]])
    ans = math.inf
    for i in range(1, n + 1):
        distance = dijkstra(graph, i)
        ans = min(ans, distance[s] + distance[a] + distance[b])

    return ans

• 플로이드 워셜 풀이

import math
def solution(n, s, a, b, fares):
    graph = [[math.inf] * (n + 1) for i in range(n + 1)]
    for fare in fares:
        graph[fare[0]][fare[1]] = fare[2]
        graph[fare[1]][fare[0]] = fare[2]
    for k in range(n + 1):
        graph[k][k] = 0
        for i in range(n + 1):
            for j in range(n + 1):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    answer = math.inf
    for i in range(1,n+1):
        answer = min(answer,graph[s][i]+graph[i][a]+graph[i][b])

    return answer