순환의 응용 - 미로찾기

순환적 사고

- 현재 위치에서 출구까지 가는 경로가 있으려면

1. 현재 위치가 출구이거나 혹은

2. 이웃한 셀들 중 하나에서 현재 위치를 다시 오지 않고 출구까지 가는 경로가 있거나

 

미로찾기(Decision Problem)

- 현재 위치가 출구이면 true 리턴

- 출구가 아니면 이웃한 셀들을 찾아보고 이훗한 셀들이 갈 수 있는 길이라면 셀들을 갖고 findPath 다시 호출

- 하지만 위의 코드로 구현하면 지금 방문한 셀이 왔던 곳인지 모르기 때문에 무한루프에 빠질 수 있음

 

따라서 방문했는지 안했는지를 알려줘야함

- 처음에 방문했다고 표시

- 이웃한 셀들 중 검사할 셀이 이미 방문했는지 확인한다.

 

- 지금 셀이 벽인지와 방문했는지를 체크

- 지금 셀이 출구면 true리턴

- 출구가 아니면 방문한걸로 체크하고 이웃한 셀들 살펴봄