글 읽기 - 노드 탐색할 때 방문 여부 판단

sy980402 2년 전 0

다른 분들의 코드와, 파이썬 코테 책을 잠고해서 문제를 풀었습니다

그런데 코드에 표기해놓은 부분이 무슨 역할을 하는지, 어떤 의미가 있는지 모르겠습니다. 책에는

#현재 노드가 이미 처리된 적이 있는 노드라면 무시

라고 적혀있고, 다른 분들의 풀이를 보아도 이미 방문한 노드를 다시 방문하지 않게하기 위한 역할로 보이는데요...

1. 왜 저 코드가 '한 번 방문한 노드의 재방문'을 막을 수 있는지 모르겠으며

2. 그럼에도 왜 저 부분을 그냥 지워도 문제없이 정답처리가 되는지 모르겠습니다!

도움 주시면 감사하겠습니다

from sys import stdin
import heapq
INF = int(1e9)

v, e = map(int, stdin.readline().split())
s = int(stdin.readline())
graph = [[] for _ in range(v+1)]

#간선 정보 입력
for i in range(e):
    a, b, c = map(int, stdin.readline().split())
    graph[a].append((c,b))

dist = [INF for _ in range(v+1)]

h = []
heapq.heappush(h, (0,s))
dist[s] = 0

while h:
    d, cur = heapq.heappop(h)
    
    #--------이 부분이 무슨 의미인지 모르겠습니다--------#
    if dist[cur] < d:
        continue
    #--------이 부분이 무슨 의미인지 모르겠습니다--------#
    
    for weight, nxt in graph[cur]:
        cost = dist[cur] + weight #현재 노드를 거쳐서 가는 경우
        if cost < dist[nxt]:
            dist[nxt] = cost
            heapq.heappush(h,(dist[nxt], nxt))

#정답 출력
for i in range(1,v+1):
    print(dist[i] if dist[i]<INF else "INF")

slah007 2년 전 1

말 그대로 큐에 같은 노드가 여러 번 들어가는 경우 같은 노드로부터 시작하는 28~32줄의 탐색을 방지하기 위해서입니다.

다음과 같은 입력을 생각해봅시다.

4 4

1 2 2

1 3 7

2 3 3

3 4 5

처음에 1->3으로 큐에 업데이트가 되지만 이후 1->2, 2->3으로 다시 큐에 업데이트가 됩니다. 이때 3에서 d = 5인 값으로 한 번 28~32줄을 실행하면 d = 7으로 다시 28~32줄을 실행할 필요가 없습니다.

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

문제

문제

출처

ICPC

노드 탐색할 때 방문 여부 판단

sy980402 2년 전 0

slah007 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말