0805jw   1년 전

x가 2x가 될 때는 cost = 0 이라 큐에 먼저 넣어야되는 건 이해했는데, x-1, x+1 사이에서도 우선순위가 왜 존재하는지 모르겠습니다.

순서를 바꾸니 44%에서 틀리고, 밑에 코드 그대로 제출하니 맞았습니다.

siyamaki   1년 전

4 6을 입력하면 2가 나옵니다.

한번 방문한 곳을 다시는 못 가고 있기 때문에 4 > 3 > 6이 더 빠르지만 4 > 5 > 6으로 먼저 도착해버려서 그렇습니다.

sianke1991   1년 전

siyamaki님

x+1을 먼저 방문하면 반례가 존재함을 알 수 있습니다.

x-1을 먼저 방문했을 때 정답이 되는 이유를 알 수 있을까요?

siyamaki   1년 전

-1을 한 이후 *2를 하였을 때 더 적은 cost로 이동 가능하기 때문입니다(10 > 14인 경우도 반례)

wizardrabbit   1년 전

본 문제의 경우 단순히 너비 우선 탐색(BFS)을 사용해서는 정답을 받을 수 있는 것이 보장되지 않는 문제입니다. 왜냐하면 너비 우선 탐색 알고리즘은 모든 간선의 가중치가 $1$일 경우에만 성립하기 때문입니다. 그러나 본 문제는 $x - 1$ 또는 $x + 1$로 이동하는 경우를 가중치 $1$, 순간이동을 해 $2 \times x$로 이동하는 경우를 가중치 $0$으로 보기 때문에 이 조건에 위배됩니다. 질문자님이 각 방법의 방문 순서를 바꿔 정답을 받으신 것도 해당 문제 상황과 어쩌다 잘 맞아 정답을 받으셨을 뿐 문제 상황이 조금만 달라지면 바로 틀릴 수도 있는 방법으로 보입니다.

따라서 이 이유로, 여러 종류의 가중치를 다룰 수 있는 0-1 너비 우선 탐색을 사용하시거나, 데이크스트라 알고리즘을 사용하여 본 문제를 푸는 경우가 많습니다. 개인적으로는 새로 배워야 할 지식이 별로 없고 현재 코드에서 조금만 개조하면 바로 사용이 가능한 0-1 너비 우선 탐색을 추천드려요.

 이 질문에 대한 답변을 한때 자세히 적어둔 적이 있었어서, 링크를 첨부해 드릴게요. 왜 단순 너비 우선 탐색이 통하지 않는지를 그림으로 끄적여 본 적이 있었어요.

여담으로 순간이동을 하는 경우를 높은 우선순위로 보고 먼저 큐에 넣으신다고 하셨는데, 큐의 뒤에 넣는 경우이기 때문에 여전히 완전하지 않아요. 0-1 너비 우선 탐색의 경우 아예 큐의 맨 앞에 해당 원소를 넣는 방법을 씁니다.

이해에 도움이 되셨으면 좋겠습니다!

0805jw   1년 전

다익스트라를 쓰는게 여러모로 편하군요 ,, 답글 감사합니다

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