저도 궁금해서 해봤더니 진짜로 그렇네요;;
13549번 - 숨바꼭질 3
원래 이 문제는 단순한 BFS를 요구하는 문제가 아닙니다. 왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문입니다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐입니다. 왜 하필 이 순서로 하면 항상 정답이 나오는가를 증명하는 건 매우 복잡한 일입니다.
이 문제를 보다 일반화된 경우 (가중치가 0인 간선이 있는 경우)에 대해 해결하려면, 즉, 이 문제의 의도대로 풀려면 다음과 같은 방법들을 사용할 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
morpheus 4년 전 7
안녕하세요 최근에 알고리즘 문제를 풀기 시작한 코딩 초보입니다.
숨바꼭질3 문제를 풀다가 생긴 의문인데요.
BFS에서 현재 수빈이의 위치를 loc이라 할 때,
큐에 넣는 순서를 loc * 2, loc - 1, loc + 1 순으로 하면 정답으로 뜨는데
왜 아래 코드처럼 loc * 2, loc + 1, loc - 1 순으로 큐에 삽입하면 오답으로 처리되는 건가요?
loc * 2를 큐에 가장 먼저 넣어야 하는 이유는 알겠지만 왜 loc - 1과 loc + 1에도 순서가 필요한지 궁금합니다.
(참고로 1697-숨바꼭질 문제에선 loc + 1과 loc -1의 삽입 순서를 바꿔도 모두 정답으로 처리되었습니다.)