본문 바로가기
Problem Solving/백준

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

by sohyunwriter 2021. 6. 17.

Question.

 

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

 

 


Answer.

 

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

 

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

 

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

*최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스

sohyunwriter.tistory.com

 

다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 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

I am reading "Algorithms Design" By Eva Tardos and in chapter 3 it is mentioned that adjacency matrix has the complexity of O(n^2) while adjacency list has O(m+n) where m is the total number of edg...

stackoverflow.com