morpheus   4년 전

안녕하세요 최근에 알고리즘 문제를 풀기 시작한 코딩 초보입니다.

숨바꼭질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의 삽입 순서를 바꿔도 모두 정답으로 처리되었습니다.)

qahira   4년 전

저도 궁금해서 해봤더니 진짜로 그렇네요;;

djm03178   4년 전

원래 이 문제는 단순한 BFS를 요구하는 문제가 아닙니다. 왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문입니다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐입니다. 왜 하필 이 순서로 하면 항상 정답이 나오는가를 증명하는 건 매우 복잡한 일입니다.

이 문제를 보다 일반화된 경우 (가중치가 0인 간선이 있는 경우)에 대해 해결하려면, 즉, 이 문제의 의도대로 풀려면 다음과 같은 방법들을 사용할 수 있습니다.

  • 다익스트라 알고리즘
  • 0-1 BFS: 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
  • * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

morpheus   4년 전

답변 감사합니다!

제시해주신 세 가지 방법 중 deque를 사용해서 loc * 2인 경우만 맨 앞에 삽입해서 풀었더니

loc - 1, loc + 1의 삽입 순서와는 상관없이 모두 정답으로 처리되네요!

덕분에 잘 해결됐습니다.

wony6731   4년 전

djm03178님 덕분에 저도 궁금했던 부분 바로 해결하였습니다!

그런데 하나 질문이 있는데 말씀하신 세가지 방법 중 세번째 방법을 사용하면

메모리 초과가 발생하지는 않나요???

djm03178   4년 전

방문 체크만 잘 하면 그럴 일은 없습니다. 어차피 큐에 들어갈 수 있는 정점은 겨우 10만 개니까요.

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