4 6을 입력하면 2가 나옵니다.
한번 방문한 곳을 다시는 못 가고 있기 때문에 4 > 3 > 6이 더 빠르지만 4 > 5 > 6으로 먼저 도착해버려서 그렇습니다.
13549번 - 숨바꼭질 3
본 문제의 경우 단순히 너비 우선 탐색(BFS)을 사용해서는 정답을 받을 수 있는 것이 보장되지 않는 문제입니다. 왜냐하면 너비 우선 탐색 알고리즘은 모든 간선의 가중치가 $1$일 경우에만 성립하기 때문입니다. 그러나 본 문제는 $x - 1$ 또는 $x + 1$로 이동하는 경우를 가중치 $1$, 순간이동을 해 $2 \times x$로 이동하는 경우를 가중치 $0$으로 보기 때문에 이 조건에 위배됩니다. 질문자님이 각 방법의 방문 순서를 바꿔 정답을 받으신 것도 해당 문제 상황과 어쩌다 잘 맞아 정답을 받으셨을 뿐 문제 상황이 조금만 달라지면 바로 틀릴 수도 있는 방법으로 보입니다.
따라서 이 이유로, 여러 종류의 가중치를 다룰 수 있는 0-1 너비 우선 탐색을 사용하시거나, 데이크스트라 알고리즘을 사용하여 본 문제를 푸는 경우가 많습니다. 개인적으로는 새로 배워야 할 지식이 별로 없고 현재 코드에서 조금만 개조하면 바로 사용이 가능한 0-1 너비 우선 탐색을 추천드려요.
이 질문에 대한 답변을 한때 자세히 적어둔 적이 있었어서, 링크를 첨부해 드릴게요. 왜 단순 너비 우선 탐색이 통하지 않는지를 그림으로 끄적여 본 적이 있었어요.
여담으로 순간이동을 하는 경우를 높은 우선순위로 보고 먼저 큐에 넣으신다고 하셨는데, 큐의 뒤에 넣는 경우이기 때문에 여전히 완전하지 않아요. 0-1 너비 우선 탐색의 경우 아예 큐의 맨 앞에 해당 원소를 넣는 방법을 씁니다.
이해에 도움이 되셨으면 좋겠습니다!
댓글을 작성하려면 로그인해야 합니다.
0805jw 1년 전
x가 2x가 될 때는 cost = 0 이라 큐에 먼저 넣어야되는 건 이해했는데, x-1, x+1 사이에서도 우선순위가 왜 존재하는지 모르겠습니다.
순서를 바꾸니 44%에서 틀리고, 밑에 코드 그대로 제출하니 맞았습니다.