최단경로인 -1*2보다 +1+1이 먼저 도착해서 visited를 찍어버려 뒤따라오는 최단경로를 차단해 버리기 때문입니다.
0-1 BFS를 쓸 때는 우선순위 큐를 이용한 다익스트라와 달리 최단경로가 반드시 제일 먼저 도착한다는 이론적 뒷받침이 없습니다. 다시 말해서, 다익스트라에서는 이미 왔었던 정점이면 continue해도 되지만 0-1 BFS에서는 한번 도착했던 정점이라도 바로 차단하지 말고 거리가 또 줄어들면 또 갱신하며 큐에 들어가도록 해야 합니다.
(2025.8.3. 추가)
일반적인 (가중치 없는) BFS에서 각 정점이 최대 1번씩만 방문되듯이, 0-1 BFS에서 각 정점은 최대 2번씩 방문될 수 있습니다. 조금 엄밀하지 않게 말하자면 2가지 버전의 BFS를 겹쳐서 돌린다고 생각할 수도 있습니다. 이때 0짜리 간선을 타고 오는 길은 반드시 큐의 앞으로, 1짜리 길은 큐의 뒤로 넣음으로 인해 그 2가지 버전 사이에 순서가 꼬이지 않는 것입니다.

james2012 2년 전 1
맞은 코드입니다. 그런데 moves = [cx*2, cx-1, cx+1] 부분을 [cx*2, cx+1, cx-1]로 바꾸면 틀립니다. 두 코드에서 각각 값이 다르게 나오는 입력값이 있나요?