[백준 1753] 최단경로 - python (solved.ac - 골드 5)

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

풀이

문제를 보았을때 알수있는 힌트

문제를 보면 그래프 문제라는 것을 알수있다. 또한 방향이 정해져있고, 정점으로가는 최단 경로를 구하는 문제이다.

간단하게 생각하면 BFS나 DFS로 풀면 되지 않을까? 생각하고 풀면 시간초과가 난다.

리스트로 정리해서 코드를 돌리면 최단 거리가 아닌 것들도 다 건드리면서 계산 되기때문이다. 또한 필요한 최단 경로만 알면 되기 때문이기도 하다.

이때 최대한 짧은 거리를 우선적으로 수행하면 뒤에 쌓인 긴 거리들은 수행안하고 넘어가게 된다. 이를 위해서는 정렬을 해야하는데 반복문안에 반복적으로 정렬은 하는 것은 비효율적이다.

이때 사용하면 되는 것이 heapq 라이브러리를 이용한다. 자동으로 정렬을 해주고 맨 앞에 최소값을 가지고 있다.

이렇게 최단 경로 문제는 다익스트라 알고리즘이라고 생각하면 된다.

다음에 알고리즘 관련해서 다익스트라 알고리즘도 작성해 놓고 기억해야할듯하다.

단순하게 생각하면 bfs와 dp,heapq의 조합이 다익스트라 알고리즘이라고 생각하면 되서 어렵지는 않다.

import sys
import heapq
input = sys.stdin.readline

V,E = map(int,input().split())
start = int(input())

INF = int(1e9)
graph=[[] for _ in range(V+1)]
graph_distance=[INF for _ in range(V+1)]

# print(graph_distance)

for i in range(E):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))

q = []
heapq.heappush(q,(0,start))
graph_distance[start]=0

while q:
    v= heapq.heappop(q)
    if graph_distance[v[1]]>=v[0]:
        for i in graph[v[1]]:
            cost = graph_distance[v[1]]+i[1]
            if cost<graph_distance[i[0]]:
                graph_distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))

for i in graph_distance[1:]:
    if i==INF:
        print("INF")
    else:
        print(i)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1753.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리