글 읽기 - 다익스트라 알고리즘

wowjd123589 2년 전 0

21번째 줄의

if dist[ev] != ew: continue 질문드리고 싶습니다

dist[ev] != ew인 경우경우는 다시 while문으로 돌아가서 heap에서 다시 pop을 합니다
dist[ev] == ew인 경우는 continue의 밑줄을 실행하며 ev에 연결된 노드를 처리합니다

질문1)코드자체는 이해가 가는데 각각의 경우 왜위와같이 하는건가요?

질문2) !=말고

if dist[ev] > ew:

if dist[ev] < ew:

로 고쳐도 다 맞네요.. 왜그런거죠?..

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

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

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

# 시작점 초기화
dist[K] = 0
heap = [[0,K]]

while heap:
    ew, ev = heapq.heappop(heap)
    if dist[ev] != ew: continue
    for nw, nv in edge[ev]:
        if dist[nv] > ew + nw:
            dist[nv] = ew + nw
            heapq.heappush(heap, [dist[nv], nv])

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

qhsl1213 2년 전 0

continue로 걸러주는 이유는, 그 노드까지의 최단거리를 마지막으로 업데이트한 최신값이 아닌, 옛날 값들이 큐에 들어있을 수 있기때문입니다. 그런경우에는 그 값을 버려야하므로 큐에 있는 다음 값을 뽑습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다익스트라 알고리즘

wowjd123589 2년 전 0

qhsl1213 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말