알고리즘/백준[baekjoon]

[baekjoon] 백준 1753번 : 최단경로 (by python 파이썬) 다익스트라 dijkstra

코딩하는이씨 2022. 8. 19. 15:29
728x90
반응형

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

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가

www.acmicpc.net

 

정답 code

#최단경로
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    visit = [INF] * (v+1)
    visit[start] = 0
    while q:
        dist , node = heapq.heappop(q)
        if visit[node] >= dist:
            for  node_index, node_time in graph[node]:
                time = node_time + dist
                if time < visit[node_index]:
                    visit[node_index] = time
                    heapq.heappush(q, (time,node_index))
    
    return visit

v,e = map(int,input().split())
k = int(input())
graph = [[] for _ in range(v+1)]

for _ in range(e):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    
x = dijkstra(k)

for i in range(1,v+1):
    if x[i] < INF:
        print(x[i])
    else:
        print('INF')

 

solution

최근 최단경로 문제들을 풀면서 다익스트라 알고리즘을 익혀 쉽게 풀어낼 수 있었다.

최단경로 말고도 따로 조건이 있진 않아서 출력시에 최단 경로가 있는경우와 없는 경우만 구분하여 출력해주면 되는 문제였다.

 

처음엔 다익스트라 문제가 힘들었지만 계속 연습하다 보니 이제 꽤 편하게 풀 수 있는 알고리즘이 된 것 같다.

 

728x90
반응형