1697번 - 숨바꼭질
BFS를 이용하여 구현하던 중, 메모리 초과를 몇 번을 겪다가 겨우 통과를 했습니다.
흥미로운 점은 메모리 문제를 해결하던 중 탐색 범위를 n, k의 범위와 똑같이 0 ~ 100,000으로 잡아도 된다는 점입니다.
문제에서 제시된 것은 분명 시작점과 종점의 범위이고, 중간에 거쳐갈 수 있는 숫자의 범위에 대해서는 언급이 없습니다.
그럼에도 통과가 가능하다는 것은 최단거리에 도달하기 위해 x < 0 또는 x > 100,000인 수를 거쳐야 하는 해가
어떤 n과 k에 대해서도 존재하지 않는다는 뜻인데, 이를 증명하는 방법을 잘 모르겠습니다.
도움을 주신다면 감사드리겠습니다.
놀라운 방식으로 증명했지만 더 좋은 답변 링크를 첨부합니다 https://www.acmicpc.net/board/...
감사합니다! 2년 전 글 중에 있었군요. 덕분에 이해가 되었습니다.
댓글을 작성하려면 로그인해야 합니다.
rapaeljin 7달 전
BFS를 이용하여 구현하던 중, 메모리 초과를 몇 번을 겪다가 겨우 통과를 했습니다.
흥미로운 점은 메모리 문제를 해결하던 중 탐색 범위를 n, k의 범위와 똑같이 0 ~ 100,000으로 잡아도 된다는 점입니다.
문제에서 제시된 것은 분명 시작점과 종점의 범위이고, 중간에 거쳐갈 수 있는 숫자의 범위에 대해서는 언급이 없습니다.
그럼에도 통과가 가능하다는 것은 최단거리에 도달하기 위해 x < 0 또는 x > 100,000인 수를 거쳐야 하는 해가
어떤 n과 k에 대해서도 존재하지 않는다는 뜻인데, 이를 증명하는 방법을 잘 모르겠습니다.
도움을 주신다면 감사드리겠습니다.