미로찾기(백트래킹, backtracking) - 모든 경로 출력

#include<stdio.h>

int map[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2},
    {2, 0, 0, 0, 0, 0, 0, 0, 2},
    {2, 0, 2, 2, 0, 2, 2, 0, 2},
    {2, 0, 2, 0, 0, 2, 0, 0, 2},
    {2, 0, 2, 0, 2, 0, 2, 0, 2},
    {2, 0, 0, 0, 0, 0, 2, 0, 2},
    {2, 2, 0, 2, 2, 0, 2, 2, 2},
    {2, 0, 0, 0, 0, 0, 0, 0, 2},
    {2, 2, 2, 2, 2, 2, 2, 2, 2}};

int visit(int x, int y);
void print_path();

int success;
int start_x, start_y;
int end_x, end_y;
int sp, ri[100], rj[100];

void main()
{
 sp = 0;
 start_x = 1;
 start_y = 1; // 시작지점
 end_x = 7;
 end_y = 7;  // 최종도착지점
 
 success = 0;
 
 printf("미로 찾기\n");
 
 if(!visit(1,1))
  printf("출구를 찾을 수 없습니다.");
}

int visit(int x, int y)
{
 map[x][y] = 1;      // 지나간 위치를 표시
 ri[sp] = x;
 rj[sp] = y;
 sp++;    // 현재의 위치를 저장하고 스택 크기를 늘린다.
      // 밑에 visit를 네방향으로 했을때 도착지점이 나오지 않으면
      // 'sp--;' 를 함으로써 현재의 위치를 삭제한다.
      // 이는 목표지점까지 가는데 현재의 위치는 의미가 없으므로
      // 제거하는 것이다.
 
 if( x == end_x && y == end_y)   // 최종 도착지점
 {
  print_path();
  success = 1;
 }
 
 if( map[x][y+1] == 0)
  visit(x, y+1);
 if( map[x+1][y] == 0)
  visit(x +1, y);
 if( map[x][y-1] == 0)
  visit(x, y -1);
 if( map[x-1][y] == 0)
  visit(x-1, y);
 
 sp--;    // 현재의 위치는 목표지점을 찾아가는데 의미가 없으므로 삭제한다.
 map[x][y] = 0;
 return success;
}

void print_path()
{
 static int path = 1;
 int k;
 
 printf("path = %d\n", path++);  // 지나간 위치 출력
 for(k =0; k < sp; k++)
  printf("(%d,%d) ", ri[k], rj[k]);
 printf("\n");
}