문제 소개

• 백준 1753
• input : 방향 그래프, 시작 정점

5 6 # 정점의 개수 V 간선의 개수 E
1 # 시작 정점 번호 K
5 1 1 # (u, v, w) u에서 v로 가는 가중치 w인 간선
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

• output : 시작점에서 다른 모든 정점으로의 최단 경로

0
2
3
7
INF

문제에 사용한 알고리즘

• 다익스트라
  • 이유 : 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램

문제 아이디어

• 다익스트라에서 노드를 방문할 때 우선순위 큐를 사용(개선된 다익스트라)
  • 기존 다익스트라 병목(시작 노드와 가장 가까운 노드 선형탐색) 해결 위해

문제에 사용한 자료구조

• 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
  • 구현 : 힙(heapq)

코드

import heapq

INF = int(1e9)
def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

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

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

graph = [[] for _ in range(V+1)]
distance = [INF for _ in range(V+1)]

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

dijkstra(K)

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