메모리를 쓰지 않고 격자형 미로를 탐색하는 법
조회수 798회
출발지점 불명. 목적지점 불명, 그러나 맵은 유한하며, 목적지는 반드시 한 개 존재함. 경로는 무조건 연결되어 있음이 보장. 자신의 좌표를 알 수 없음.
좌선법(왼손을 벽에 항상 닿게 하는 것)은, 루프가 존재할 경우 루프를 무한히 타게 됨. 아래처럼.
조건은 메모리를 쓰면 안됨. 또한, 분기마다 새로 쓰레드를 발생시키는 것은, 사실상 메모리를 사용하는 것이기에 불가.
매 셀은 최소한 2개의 통로를 가지며, 목적지만 통로가 하나임.
과연 방법이 있을지..... 아이디어 있으신 분들께 부탁드립니다.
댓글 입력