C언어 DFS 미로 최단경로 구하기(escape the maze in C)

DFS 미로 최단경로

- DFS 알고리즘을 이용하여 주어진 미로의 최단 경로를 구하라.

제한 사항

- N X N 미로의 크기 N은 5 ~ 10

- 각 수행 시간은 10msec를 넘지 않도록 한다.

입력과 출력

- 입력은 맨 처음은 테스트 횟수(TC), 그 다음부터 N X N 미로의 크기 N 을 입력받고

미로의 원소들을 각각 입력받는다.( 입력은 첨부된 input.txt 파일을 이용한다. ) input.txt

시작점(1), 목표점(2), 길(0), 벽(7) = 이동할 수 없는 지점

- 출력은 우측의 출력 예를 참고한다.

입력 예	출력 예
5 5 7 1 7 7 7 7 0 0 0 7 7 0 7 0 7 7 7 0 0 7 7 7 7 2 7 .......	#1, ? msec. answer = 6 #2, ? msec. answer = 7 #3, ? msec. answer = 12 #4, ? msec. answer = 15 #5, ? msec. answer = 19

 

 

 

#include <stdio.h> #include <time.h> #define NMAX 10 #define WALL 7 #define ROUTE 2 #define START 1 #define END  2 #define VISITED 3 typedef struct xy{  int x;  int y; }XY; int map[NMAX][NMAX]; int result; XY s; void dfs( XY, int); int main( void) {  time_t time_s, time_e;  int processtime;  int T,TC;  int N;  int i, j;  freopen("input.txt","r",stdin);  scanf("%d", &TC);  for( T = 0 ; T < TC ; T ++)  {   time_s = clock(); // get the starting time.   scanf("%d", &N);   for( i = 0 ; i < N ; i ++)   {    for( j = 0 ; j < N ; j ++)    {     scanf("%d", &map[i][j]);     // save the position of starting point.     if( map[i][j] == START)     {      s.y = i;      s.x = j;     }    }   }   result = -1;   dfs( s, 0);   time_e = clock(); // get the ending time.   // calculate the time   processtime = (int)(time_e - time_s);   printf("#%d, %d msec. ",T+1 , processtime);   printf("answer = %d\n", result);  }  return 0; } void dfs( XY v, int w) {  XY temp;  int i;  // if this position is the same with END.  if( map[v.y][v.x] == END)  {   // update the shortest distance.   if( w < result || result == -1)   {    result = w;   }   return 0;  }  // mark this position as VISITED.  map[v.y][v.x] = VISITED;  // inspect the position located below.  if( map[v.y+1][v.x] <= ROUTE)  {   temp.x = v.x;   temp.y = v.y+1;   dfs( temp, w+1);  }  // inspect the position on the left.  if( map[v.y][v.x-1] <= ROUTE)  {   temp.x = v.x-1;   temp.y = v.y;   dfs( temp, w+1);  }  // inspect the position on the right.  if( map[v.y][v.x+1] <= ROUTE)  {   temp.x = v.x+1;   temp.y = v.y;   dfs( temp, w+1);  }  // inspect the position on the top.  if( map[v.y-1][v.x]  <= ROUTE && v.y -1 >= 0)  {   temp.x = v.x;   temp.y = v.y-1;   dfs( temp, w+1);  } }