kykapple   3년 전

각 지역에서 BFS를 수행하여 수색 범위를 넘지 않으면 계속 탐색하도록 코드를 작성하였습니다.

반례를 최대한 찾아보려 했지만 쉽지 않네요ㅠㅠ

반례 혹은 오류에 대한 지적 부탁드립니다.

comseung18   3년 전

간선의 길이가 모두 같지 않기 때문에 단순한 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년 전

되지 않는 이유를 정확히 알려주셔서 감사합니다! 답변 주신 것을 기반으로 다시 풀어보도록 하겠습니다:)

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