james2012   2년 전

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

zenith82114   2년 전

최단경로인 -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가지 버전 사이에 순서가 꼬이지 않는 것입니다.

leeingyun96   2년 전

-1, *2와 +1, +1은 동일한 거리에 도달하지만 총 비용이 다릅니다. (동일 거리 기준) *2를 최대한 많이 쓰는 게 유리한데 이걸 (동일 거리 기준) 많이 쓰기 위해서는 반대되는 방향, 즉 -1이 많을수록 유리합니다. 그래서 -1이 +1보다 먼저 와야 합니다.

 

이건 좀 ad hoc스러운 풀이고 윗댓처럼 갱신 다시 해주는 게 조금 더 체계적인 풀이가 되겠네요. 지금 생각난 건데 n, k의 범위가 음수로 확장된다면 본문의 풀이로는 못 풀고 윗댓의 방식으로만 풀 수 있을 것 같네요.

(추가)
bfs는 child 노드를 엿볼 때(좋은 표현은 아니지만 이해되실 겁니다.) 그 child 노드를 지나는 경로가 최단 경로임이 보장되고, 이때 방문 처리를 해주고 큐 안에 넣어도 됩니다.
다익스트라는 child 노드를 엿볼 때 그 child 노드를 지나는 경로가 최단 경로임이 보장되지 않고, 따라서 이때 방문 처리를 해주면 안 됩니다.(단 자명하게 거리가 같거나 이상이라면 무용이니 힙 안에 안 넣어도 됩니다.) 힙 안에 넣은 뒤 힙에서 뺄 때 방문 처리를 해줘야 합니다. 그리고 힙에서 노드들이 나올 때 이미 방문 처리가 되었으면 continue해줘야 합니다. 코드를 다시 보시면 일반 bfs랑 일반 다익스트라랑 방문 여부 확인하는 코드의 위치가 다를 겁니다. 이래서 다익스트라 구현할 때 오류가 많은 거고요.
0-1 bfs는 다익스트라와 동일해야 합니다.

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