메모리를 쓰지 않고 격자형 미로를 탐색하는 법

조회수 80회

출발지점 불명. 목적지점 불명, 그러나 맵은 유한하며, 목적지는 반드시 한 개 존재함. 경로는 무조건 연결되어 있음이 보장. 자신의 좌표를 알 수 없음.

좌선법(왼손을 벽에 항상 닿게 하는 것)은, 루프가 존재할 경우 루프를 무한히 타게 됨. 아래처럼. 이미지

조건은 메모리를 쓰면 안됨. 또한, 분기마다 새로 쓰레드를 발생시키는 것은, 사실상 메모리를 사용하는 것이기에 불가.

매 셀은 최소한 2개의 통로를 가지며, 목적지만 통로가 하나임.

과연 방법이 있을지..... 아이디어 있으신 분들께 부탁드립니다.

  • 쥐를 집어넣고 길찾기를 시키는 게 더 빠르겠는데요;; 해법이 있기는 있나?? 엽토군 2019.4.17 08:48
  • 아이디어라고 하기에도 뭐하지만 그냥 랜덤 돌리는것 말고는 해법이 있나 싶습니다. digda 2019.4.18 06:51

답변을 하려면 로그인이 필요합니다.

Hashcode는 개발자들을 위한 무료 QnA 사이트입니다. 계정을 생성하셔야만 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 계정을 생성하셔야만 글을 작성하실 수 있습니다.