미로찾기 문제

문제의 의미

미로찾기란 시작점에서 종료지점까지의 경로를 찾는 문제이다.

아이디어

시작지점에서 종료지점까지 가려면 현재지점에서 다음에 갈 수 있는 지점들을 탐색해야한다.

그림에서 1은 벽으로 갈 수 없는 곳, X는 이미 지나온 곳, O는 갈 수 있는 곳이다. 현재지점이 종료지점인지 검사한 후, 아니라면 지나온 곳으로 표시하고 주변 지역들을 탐색할 곳으로 탐색리스트에 등록을 한다.

탐색리스트에서 후보를 하나 꺼낸 후 종료지점인지, 종료지점이 아니라면 갈 수 있는 곳인지 여부를 확인하고 종료지점에 도달할 때까지 로직을 반복한다.

설계

while true
	후리스트에서 후보 하나 꺼내기
	
	if 종료지점
		종료
	
	if !벽 and !지나온 곳
		지나온 곳 표시
		주변 지역을 후보로 후보리스트에 등록

후보리스트에 등록할 때 재귀호출을 사용하는 방법과 스택을 사용하는 방법이 있다.