BFS는 큐에 넣는 순간 방문 처리해서 레벨 순서를 보존한다
무가중치 최단 거리에서는 최초 enqueue 시점의 거리가 곧 최단 거리입니다.
레벨 순서
dist 0
1
dist 1
23
dist 2
45
핵심: 방문 체크를 늦추면 같은 정점이 큐에 여러 번 들어가 BFS의 레벨 의미와 메모리 사용이 흔들립니다.
무가중치 최단 거리에서는 최초 enqueue 시점의 거리가 곧 최단 거리입니다.
핵심: 방문 체크를 늦추면 같은 정점이 큐에 여러 번 들어가 BFS의 레벨 의미와 메모리 사용이 흔들립니다.