예제 그래프
0
1
2
3
4
5
edges: 0-1, 0-2, 1-3, 2-4 / start=0
dist는 enqueue 순간 확정해야 중복 방문이 사라진다
큐에 넣을 때 방문 처리와 거리 기록을 함께 해야 같은 정점이 여러 번 들어가지 않는다.
큐와 거리 변화
startq=[0]dist[0]=0
pop 0push 1,2dist=1
pop 1push 3dist[3]=2
| 시점 | 해야 할 일 | 늦으면 생기는 문제 |
|---|---|---|
| 발견 | dist[nxt]가 -1인지 확인한다. | 이미 발견된 정점을 또 후보로 본다. |
| enqueue | dist[nxt] = dist[cur] + 1 | 큐에 같은 정점이 여러 번 들어간다. |
| dequeue | 이미 확정된 거리로 이웃만 살핀다. | 거리 덮어쓰기와 중복 계산이 생긴다. |