간선의 길이가 모두 같지 않기 때문에 단순한 bfs 로는 최단경로 순서로 방문을 하지 않을 수 있습니다.
예를 들어 거리제한이 15이라고 하면,
1번도시 -> 2번도시 거리가 10 이고
1번도시 -> 3번도시 거리가 3 이고
3번도시 -> 2번도시 거리가 3 이고
2번도시 -> 4번도시 거리가 6 이라고 합시다.
그러면 1번 -> 3번 -> 2번 -> 4번 순서로 방문하면 1번도시 -> 4번도시 사이의 거리는 12이므로 아이템을 얻을 수 있어야 하지만 위와 같이 bfs 를 하게되면
1번도시를 방문 한 뒤에 2번 도시와 3번 도시가 queue에 push 가 되고 방문하게 될텐데
2번 도시를 방문했을 때 4번도시가 거리가 안된다고 생각하여 방문을 하지 않게 됩니다.
그리고 3번 도시를 방문하고 탐색이 종료 되겠죠.
3번 도시를 방문했을 때, 2번 도시와의 거리가 변할 수 있기 때문에 4번 도시를 방문할 수 있는데 이 가능성이 무시된겁니다.
그래서 간선의 길이가 모두 같지 않을 때 최단 거리 순서로 방문하는 "다익스트라" 알고리즘이 있으니 참고하면 좋을 것 같습니다.
kykapple 3년 전
각 지역에서 BFS를 수행하여 수색 범위를 넘지 않으면 계속 탐색하도록 코드를 작성하였습니다.
반례를 최대한 찾아보려 했지만 쉽지 않네요ㅠㅠ
반례 혹은 오류에 대한 지적 부탁드립니다.