문제 해결 전략

=> 탑다운

최악의 경우.

• n * m 미로인데 크기가 500 X 500 이다.
  -> 칸 하나를 최악의 경우 빠져나오는데 는 250000 이다.
  지그재그로 해서 빠져 나올 수 있따...
  그런데 모든 정점 까지 해야 하므로
  250000 X 250000 이다.... 어마어마 하다.

• 입력 예제를 보면서, 재귀를 통해 nextPos로 접근을 하면서 통과되면, 반환 받아서 정보를 저장하는 구조로 작성해야 겠다는 생각을 함.

• 입력 1번.
  

• 입력 3번을 보면, 출력이 0이다.
  : 순환 구조를 이루고 있다....
  

최적 부분 구조를 생각해보자.

1. 순환 구조 어떻게 처리할까?

: 방문 처리를 확인해서 순환구조이면 0을 반환하게 함.

2. 방 탈출 하는 경우

: 범위를 벗어나면 1을 반환하게 함.

3. 메모이제이션을 사용하면 좋을 듯 하다.

: 탑다운 방식으로 진행하려고 한다.

• 입력 예제 4번인데 빨간색 칠해진 부분은 순환구조이므로
  빨간색 그려진 정점은 카운팅 불가하다.
  : 0,0에서 부터 시작한 진행상황인데,

-> 이렇게 메모이제이션으로 표기하게 되면 0,1에 해당하는 친구 입장에서는 어차피 시작 해봤자, 순환구조임을 알게 되므로, 할 필요가 없어진다.

코드

• ㅇㅇ
  
  

• 중요한 부분
  : visited 이렇게 설정해도 되네...
  -> 진입해서 나오는 부분은 동일하기 때문에 이렇게 해도 된다.