스택을 이용한 미로찾기

이번에는 스택을 이용해 미로찾기 게임을 만들어보자.

이는 추후 그래프에서 깊이우선탐색과도 큰 연관이 있는데,

미로는 이와같이 주변 벽을 1, 갈수있는 통로를 0, 그리고 시작점을 (1,1)로 두는 미로로 주어진다.

 

원리는 이렇다

방향을 8등분하여 각각의 이동하는 좌표를 만들어준다. 우리는 N(북쪽방향)부터 시계방향으로 탐색할 것이다.

 

시작점해서 출발하면 일단 들린곳은 mark 하게 될것이다.

앞으로 시계방향으로 탐색하며, 0인 부분은 일단 들어가고 본다.

또한 들리자마자 mark하게 될텐데, 이는 mark하지않으면 이전 통로로 이동하는 무한반복 Loop에 빠지게 된다.

 

에를들어 위와같은 상태에서 direction이 3일때 통로가 발견되었으면, 

 

이렇게 그지점을 방문표시하고 방향까자 포함해 스택에 넣는다. (다음에 돌아왔을때 저장된 방향부터 다시 탐색하기 위함이다.)

 

 

결과는 미로와 미로찾기 경로를 확인가능하다.