Visit(방문) 체크해주기 -> 다익스트라, bfs, dfs 등

1. BFS

큐에 넣을 때 방문 체크 해준다

(->안 그러고 다른 방법도 있긴 한데.. 그럼 봤던 노드를 또 봐야 함!)

 

위의 그림처럼 노드가 중복으로 들어가서 (BFS에서 노드는 큐에 처음 들어간 순간이 무조건 최단거리 확정임) 굳이 또 봐주는 수고를 해야하므로 그런일을 없애기 위해서 그냥 큐에 넣음과 동시에 visit 체크 해주기

 

 

2. DFS

문제에 따라 다르지만 보통 상관없다

 

 

3. 다익스트라

큐에서 나올때 방문 체크 해준다

 

이유:

djm03178 님의 설명

다익스트라는 큐에서 빠지기 전까지는 정점에 대한 거리 갱신이 끝난 게 아닙니다. 한 번 우선순위 큐에 어떤 거리로 지정되어 들어갔어도 다른 정점에 의해 거리가 다시 갱신될 수 있습니다. 그러니 큐에 넣는 순간에 바로 방문 체크를 해버리면 안 되고 더 이상 거리 갱신이 일어나지 않을 때까지 (= 그 정점이 큐에서 나올 때까지) 놔둬야 합니다.

 

--> 참고: https://www.acmicpc.net/board/view/34516

글 읽기 - ★☆★☆★ [필독] 최단경로 (다익스트라 알고리즘) FAQ ★☆★☆★