백준 1753. 최단경로 (+파이썬 풀이)

Question.

 

최단경로 문제다. 코딩테스트에 정말 자주 나오는 문제이니 풀어보자.

 

 

---

Answer.

 

최단경로 알고리즘 중에서도 '다익스트라 알고리즘' 문제다.

 

2021.01.16 - [Computer Science/Datastructure & Algorithm] - 최단경로 알고리즘 (1) - 다익스트라 알고리즘

최단경로 알고리즘 (1) - 다익스트라 알고리즘

 

다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 snippet으로 만들어뒀다.

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(graph, pos, distance, visited, n):
    q = []

    heapq.heappush(q, (0, pos))
    distance[pos] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    return distance

def solve(n, m, pos, edges):
    graph = [[] for i in range(n + 1)]
    visited = [False] * (n + 1)
    distance = [INF] * (n + 1)

    for start, dest, cost in edges:
        graph[start].append((dest, cost))

    dijkstra(graph, pos, distance, visited, n)

    return distance

if __name__ == "__main__":
    n, m = map(int, input().split())
    pos = int(input())
    edges = [list(map(int, input().split())) for _ in range(m)]

    distance = solve(n, m, pos, edges)

    for i in range(1, n+1):
        if distance[i] == INF:
            print("INF")
        else:
            print(distance[i])

 

sol 1)
Time Complexity	O(ElogV)
Space Complexity	O(V^2)

**입력까지 고려했을 때는 그래프를 adjacency matrix로 만들었기 때문에 O(V^2)이나, 

다익스트라 알고리즘 자체의 space complexity는 O(V+E)

 

(참고) https://stackoverflow.com/questions/32608288/time-space-complexity-of-adjacency-matrix-and-adjacency-list

Time/Space complexity of adjacency matrix and adjacency list