[문제]미로 찾기

어떤 미로가 있다.
크기 : n x m
칸으로 되어 있고, 0인 칸은 열린 곳(길), 1인 칸은 막힌 곳(벽)이다.
출발점 : (1, 1)
도착점 : (n, m)
움직임이 가능한 방향 : 상, 하, 좌, 우

예)
4 x 5의 미로
00000
01110
01110
00000

문제)
미로의 모든 최단 경로를 찾는 다.
(문제를 최단 경로로 하지 않으면 loop가 생겨서 path가 무한히 많을 수 있다.)
모든 최단 경로의 경우는 display하고, count한다.

해결책)
미로를 decision tree로 바라보고 depth first search한다.
root node는 출발점이고
leaf node는 결승점 혹은 막다른 칸 혹은 이미 간 칸이다.
각 node의 child node는 4개(상,하,좌,우) 이하이다.

tree의 예)
000
000
000

(0,0)
  |                 |
(0,1)             (1,0)
  |     |           |           |
(0,2) (1,1)       (1,1)       (2,0)
  |     |     |     |           |
(1,2) (1,2) (2,1) (1,2) (2,1) (2,1)
  |     |     |     |     |     |
(2,2) (2,2) (2,2) (2,2) (2,2) (2,2)

001
100
100

(0,0)
  |      
(0,1)
  |   \
(1,1) (1,2)
  |     |
(2,1) (2,2)
  |
(2,2)

매 칸을 갈 때마다 stack에 현재 칸을 push하고
다시 traceback할 때 pop한다.

DFS search는 recursive call을 이용하여 구현한다.
(OS call stack도 이용하는 셈)
이미 온 칸 인지 볼 때도 stack의 모든 원소와 현재 칸을 뒤진다.
막다른 골목인지는 상하좌우를 살피거나, 좌표가 matrix 내부의 값인지 본다.(boundary 조건)

구현)
함수(int x, int y) { // 현재 위치 : (x,y)
if (이미 온칸?) {
   return ;
} else if (막 다른 골목)
   return ;
} else if (결승점) {
   ++(결승점 경우의 수)
   stack의 모든 원소 출력
}

stack.push((x,y))
if (오른쪽 == 0) {
   함수(x , y + 1);
}

if (아래쪽 == 0) {
   함수(x + 1 , y);
}
stack.pop();
}

해결책을 최적화 하는 방법)
모든 최단 경로의 경우의 수를 출력하지 않고 단지 count하는 것이라면
function call시 return값으로 그 칸을 지난 경우의 수 합을 return하고
모든 function은 child node의 경우의 수의 합을 return하면 된다.
dynamic programming으로 결과를 cache해서
이미 count된 좌표일 때는 저장된 결과를 return한다.