[코딩테스트] 백준 1753번: 최단경로

1. 아이디어

▪ 시작점에서 다른 모든 점으로 최단 경로 -> 다익스트라

▪ 간선 정보 인접리스트에 저장

▪ 거리배열 INF로 초기화

▪ 시작점(0,1) heap에 넣기

▪ heap이 빌때까지 while문 반복

▪ heap에서 꺼내온 받아온 edge가 최신 값인지 확인

   - 최신값 아니면 continue

   - 최신값이면

      - 해당 노드를 거쳐서 인근 노드로 가는 비용이 작으면

          - 인근 노드로 가는 비용 갱신

          - heap에 인근 노드 넣기

2. 시간복잡도

▪ log(ElogV)

3. 변수

▪ 최단 경로값 저장할 리스트: int[]

▪ 간선정보 인접리스트(가중치,다음노드): (int,int)[][]

▪ (가중치, 다음노드)를 저장할 heap

Code

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

V,E = map(int,input().split())
K = int(input())
edges = [[] for _ in range(V+1)]

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

rs = [INF for _ in range(V+1)]
rs[K] = 0
heap = [[0,K]]

while heap:
    w, node = heapq.heappop(heap)

    if rs[node] != w: continue

    for nw, next_node in edges[node]:
        if rs[next_node] > w + nw:
            rs[next_node] = w + nw
            heapq.heappush(heap, [rs[next_node], next_node])

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

1753번: 최단경로