우선순위 큐를 사용하는 건 BFS라고 할 수 없습니다. 다익스트라에 가까운 방법인데, 한 가지 빠진 것이 이미 큐에 넣은 정점이라도 실제로 방문하기 전에 거리를 또 갱신할 수 있어야 한다는 점입니다.

예시로, 2 6 과 같은 입력에서 2 - 4 - 8 - 7의 경로가 2 - 3의 경로보다 먼저 방문하게 되어, 7에서 6으로 내려가는 경로가 먼저 visited[6]을 true로 만들어버리고 이 때의 이동 횟수는 총 2가 됩니다. 하지만 똑같은 우선순위를 갖는 3에서 2배를 해서 6에 도달하면 거리가 갱신될 수 있는데도 이미 visited가 표시되어 있어 큐에 삽입 자체를 안 하게 됩니다.

이 문제를 BFS로 풀고자 한다면, 어떤 점에서 n번 점으로 이동할 때 모든 가능한 k에 대해 n*2^k 점들도 모두 한 번에 큐에 몰아서 넣는 방법을 사용하면 됩니다.

10 18 을 입력해보시면

10 -> 9 -> 18 로 1이 나와야 하는데 2가 나오고 있습니다.

tc.txt

위 파일은 질문자께서 올리신 소스에서 어떤 위치까지 가는데 비용이 얼마나 들며 이전 위치가 어디인지를 출력해주는 코드를 추가한 output입니다.

감사합니다