2021 카카오 코딩테스트 lv.3 합승 택시 요금 파이썬

다익스트라, 플로이드와샬 두가지 알고리즘으로 문제를 풀 수 있습니다.

 

 

다익스트라

import heapq

def dijkstra(s,i):
    global n,graph
    hq = [(s,0)]
    heapq.heapify(hq)

    visited = [float('inf')]*(n+1)
    visited[s] = 0

    while hq:
        now_node,now_fare = heapq.heappop(hq)
        if now_fare > visited[now_node]:
            continue
        for fare,node in graph[now_node]:
            sum_fare = now_fare+fare
            if sum_fare < visited[node]:
                visited[node] = sum_fare
                heapq.heappush(hq,(node,sum_fare))
    return visited[i]

def solution(n, s, a, b, fares):
    global graph
    graph = [[] for _ in range(n+1)]
    for c,d,f in fares:
        graph[c].append([f,d])
        graph[d].append([f,c])
    answer = float('inf')
    for i in range(1,n+1):
        answer = min(answer,dijkstra(s,i)+dijkstra(i,a)+dijkstra(i,b))
    return answer

 

 

 

플로이드와샬

def solution(n, s, a, b, fares):
    graph = [[float('inf')]*(n+1) for _ in range(n+1)]

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

    for c,d,f in fares:
        graph[c][d] = f
        graph[d][c] = f

    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    answer = float('inf')

    for i in range(1,n+1):
        answer = min(answer,graph[s][i]+graph[i][a]+graph[i][b])

    return answer

 

 

다익스트라 알고리즘은 한 노드에서 모든 다른 노드까지의 최단거리를 구하지만,

플로이드 와샬 알고리즘은 한 노드에서 모든 다른 노드까지의 최단거리를 모든 노드에 대해 구합니다.

 

다익스트라 알고리즘은 현재 상태에서 방문하지 않은 노드중 거리가 가장 가까운 노드 먼저 방문하면서 최단거리를 구합니다. 

플로이드 와샬 알고리즘은 i노드에서 j노드로 한번에 가는 거리와 i노드에서 k노드를 거쳐 j노드를 가는 거리를 비교하여 최단거리를 갱신해 줍니다.