_Mini_Project2_MAZE

maze.c

 쥐를 찾는 미니 프로젝트를 구현하였습니다.
우선 및 좌선 법이 아닌, 전체 탐색 후 최단거리를 찾아냅니다.

/*=====================================================================*/

/*   ☆★ 미니 프로젝트 : Micro Mouse (miro). ☆★              */

/*      목적 : 1.생쥐 미로 탈출!!             */

/*      기능 : -Graphic 구현.                  
     Q
         -최단거리 구현.
       그냥 무조건 북쪽기준 오른쪽 탐색
      
/*=====================================================================*/

#include<stdio.h>
#include<windows.h>
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<dos.h>

#define MAZE_SIZE 19
#define M_ROBOT "ⓜ" // 마우스를 의미하는 코드.
#define SUCCEED "♨" // 탈출 성공 자축 코드.
 
/* 방향 매크로 - 위, 오른쪽, 아래, 왼쪽 (1만큼 왼쪽 시프트 할때마다 바뀜.) */
#define UP 1  // ..00001
#define RIGHT 2  // ..00010
#define DOWN 4  // ..00100
#define LEFT 8  // ..01000

#define MAX_STACK_SIZE 200

#define EXIT_ROW 17
#define EXIT_COL 17

/* 미로 그림. -입구[1][1] , -출구[18][18] */
int maze[MAZE_SIZE][MAZE_SIZE] =
{
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },//0
{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 },//1
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 },//2
{ 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1 },//3
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1 },//4
{ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 },//5
{ 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1 },//6
{ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },//7
{ 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },//8
{ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },//9
{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },//0
{ 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1 },//1
{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1 },//2
{ 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 },//3
{ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 },//4
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 },//5
{ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1 },//6
{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },//7
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };

int Emark[MAZE_SIZE][MAZE_SIZE];  // 이동해온 자취(1을 넣어서 지나온 길임을 표시).
       

 

typedef struct{
 int row;
 int col;
 int dir;
}element;
element Estack[MAX_STACK_SIZE];  // 최단거리를 찾기위해 저장할 x좌표, y좌표, 방향.

int sx=1,sy=1;    //출발위치.
int Ecnt=200;     //마우스의 걸음수.
int Etop=0;      // stack의 맨위 인덱스.

/*======================함수들==========================*/

int get_shape(int m[][MAZE_SIZE],int x,int y);    // 벽배치에 따른 중앙벽의 모양을 리턴.
void draw_maze(int m[][MAZE_SIZE]);       // 미로를 화면에 그려주는 함수.
void gotoxy(int x, int y);         // 커서를 x,y좌표로 이동시켜주는 함수.
void print_maze(int i);          // 미로의 벽을 출력 하는 함수.

//void record(int x,int y,int dir);       // 생쥐의 이동경로를 저장하는 함수.
int still_in_maze(int x, int y);       // 생쥐가 출구좌표에 있는지 확인하는 함수.
int wall_ahead(int m[][MAZE_SIZE], int x, int y, int dir); // 앞이 막혔는지 뚫렸는지 확인 함수.
void path_maze(int maze[][MAZE_SIZE],int cnt);    // 미로 찾기 프로그램.
void foward(int *x, int *y, int dir);      // 생쥐를 앞으로 이동시키는 함수
int right(int *dir);          // 방향을 오른쪽으로 돌리는 함수
element Delete(int *top);
void Add(int *top,int x,int y,int dir);
int Dirsch(int x, int y, int dir, int top, element stack[MAX_STACK_SIZE], int cnt, int mark[][MAZE_SIZE]);
// 4방향 탐색(최단경로 찾기 함수.)
int Path(int x, int y, int dir, int top, element stack[MAX_STACK_SIZE], int cnt, int mark[][MAZE_SIZE]);
// 통로 전진. (최단경로 찾기 함수.)

 

/********************************************************/
/*    main 함수.
/********************************************************/

int main(void){
 int x=sx, y=sy, dir=UP;
 int mark[MAZE_SIZE][MAZE_SIZE]= {0};  // 이동해온 자취(1을 넣어서 지나온 길임을 표시).
 int top=0,cnt=0;
// int j;
 system("cls");
 system("chcp 949");
// clscr();
 /*  미로 생성   */
 draw_maze(maze);
 puts("");
 gotoxy(40,5);
 puts("  ====== Simulation of Micro Mouse ======");
 Sleep(200);    // 오프닝 타임.
 gotoxy(40,10);
 puts("          Press any key to start.");
 getchar();
 gotoxy(23,5);
 puts("Now... Micro Mouse run!!!!!!");
//여기를 실행 안하고 하면 되는데 이거 하고 하면 안됨
/* path_maze(maze,Ecnt); // 단순 미로찾기.
 gotoxy(23,5);
 printf("Micro Mouse..he was succeeded!!!");
//그담에 미로를 다시그리고..
// draw_maze(maze);
 Sleep(200);    // 오프닝 타임.
 for(cnt=1;cnt<=top;cnt++){
  gotoxy(x+1,y+1);
  printf("*");  // 지나온 길 체크.
  gotoxy((Estack[cnt].row)+1,(Estack[cnt].col)+1);
  printf(M_ROBOT);
  x=Estack[cnt].row,y=Estack[cnt].col;
  Estack[cnt].row=0;
  Estack[cnt].col=0;
  Estack[cnt].dir=0;
 }
 Etop=0;
 */ 
 gotoxy(23,5);
 puts("Now... Micro Mouse run!!!!!!");
 top=0;
// top의 처음 값 저장.
 Estack[top].row=x;  
 Estack[top].col=y;
 Estack[top].dir=dir;
 top++;
 gotoxy(x,y+1);  // 첫 걸음 표현.
 printf("＊"); // 스택에 저장 되있자나요 탑도 증가 되있고 바바요 ㅇㅋ?
 Ecnt++;    // 걸음 카운트 1증가.
 gotoxy(x+1,y+1);
 printf(M_ROBOT); // 생쥐 등장.
 Emark[0][1]=1;  // 현재 위치 마크 1.
 Emark[x][y]=1; 
//여기 이거 하고 밑에 포문에서 스택에 저장 된것만 돌려주려고 하는데 포문이 안 돌아가는 거 같음..
/* system("cls");
   for(j=0;j<MAX_STACK_SIZE;j++)
    printf("y = %d x = %d \n",Estack[j].col,Estack[j].row);

   getch();
 system("cls");*/
 

 Dirsch(x,y,dir,top,Estack,cnt,mark);  //최단경로.이게 오늘 한거...
 draw_maze(maze);
 x=1,y=1;
 gotoxy(x,y+1);
 printf("★");
 for(cnt=0;cnt<Etop;cnt++){
  Sleep(10);
  gotoxy(x+1,y+1);
  printf("★");  // 지나온 길 체크.
  gotoxy((Estack[cnt].row)+1,(Estack[cnt].col)+1);
  printf(M_ROBOT);
  x=Estack[cnt].row,y=Estack[cnt].col;
 }
 gotoxy(23,5);
 printf("Micro Mouse..he was succeeded!!!");
 printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t ");

 getch();
 printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\t ");

 return 0;
}
/********************************************************/
/*   4방향 탐색(최단경로 찾기 함수.)

  -인자형 : int형 x, y좌표, 방향, cnt(걸음수),
     top, element형 stack, 배열mark[][].
  -리턴형 : int.(상위 함수 path가 종료될 신호.)

/********************************************************/
int Dirsch(int x, int y, int dir, int top, element stack[MAX_STACK_SIZE], int cnt, int mark[][MAZE_SIZE])
{

 element imsi_stack[MAX_STACK_SIZE];
 int imsi_mark[MAZE_SIZE][MAZE_SIZE];
 int i=0, n=-1, row, col, j, load[4]; 
 // 반복문 카운트i, 인덱스n, (x,y)의 전진값(low,col), 통로의방향이 저장되는 배열 load[4].
 
 memcpy(imsi_mark, mark, sizeof(imsi_mark));
 for(j=0;j<MAX_STACK_SIZE;j++)
 {
  imsi_stack[j].col=stack[j].col;
  imsi_stack[j].row=stack[j].row;  
 }
 dir=UP;   // 방향 초기화 UP.
 gotoxy(21,9); //확인용 
 printf("-top=%2d /%2d stack[top]= %2d, %2d ",top,Etop,imsi_stack[top].row,imsi_stack[top].col); //확인용
    
 while(i<4){
  row=x;   // x의 전진방향을 표시할 row.
  col=y;   // y의 전진방향을 표시할 col.
  
  if((row==EXIT_ROW)&&(col==EXIT_COL)){
   gotoxy(23,5);
   printf("Micro Mouse..he was succeeded!!!");
   Etop=top;
   Ecnt=cnt;   
   for(j=0;j<MAX_STACK_SIZE;j++)
   {
    Estack[j].col=imsi_stack[j].col;
    Estack[j].row=imsi_stack[j].row;  
   }
   
   draw_maze(maze);
   return 1;
  }

 

  row = (dir == LEFT) ? --row : (dir == RIGHT)? ++row : row; // 방향이 왼쪽이나 오른쪽이면 x이동.
  col = (dir == UP)? --col : (dir == DOWN)? ++col : col;  // 방향이 북쪽이나 남쪽이면 y이동.
  gotoxy(21,8); //확인용
  printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
  
  if(!wall_ahead(maze,x,y,dir) && !imsi_mark[row][col]){
   n++;
   load[n]=dir;
  }
  right(&dir);
  Sleep(0);
  i++;
 }
 gotoxy(21,10); //확인용
 printf("-i,n,load[n]: (%2d,%2d,%2d) ",x,y,dir); //확인용
 
 Sleep(30);
 //통로 갯수n이 하나일때..
 if(n==0)
  Path(x,y,load[n],top,imsi_stack,cnt,imsi_mark);

 //통로 갯수n이 둘이상일때..
 else if(n>0){
  for(j=0; j<=n; j++){
   Sleep(0);
   gotoxy(21,7);    //확인용
   printf("-before/after(cnt)=%3d /%3d ",Ecnt,cnt); //확인용
   Path(x,y,load[j],top,imsi_stack,cnt,imsi_mark);
   gotoxy(21,8); //확인용
   printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
   gotoxy(21,9); //확인용 
   printf("-top=%2d /%2d stack[top]= %2d, %2d ",top,Etop,Estack[Etop].row,Estack[Etop].col); //확인용
  }
 }
 //통로 갯수가 없을때(막혔을때)...
 else if(n<0)
  return 0;
}
/********************************************************/
/*   통로 전진. (최단경로 찾기 함수.)

  -인자형 : int형 x, y좌표, 방향, cnt(걸음수),
    element형 stack, 배열mark[][].
  -리턴형 : int.(상위 함수가 종료될 신호.)

/********************************************************/
int Path(int x, int y, int dir, int top, element stack[MAX_STACK_SIZE], int cnt, int mark[][MAZE_SIZE])
{
 int row, col; //i;
 row=x;   // x의 전진방향을 표시할 row.
 col=y;   // y의 전진방향을 표시할 col.
 Sleep(10);
 gotoxy(23,5);
 puts("Now... Micro Mouse run!!!!!!");

 row = (dir == LEFT) ? --row : (dir == RIGHT)? ++row : row; // 방향이 왼쪽이나 오른쪽이면 x이동.
 col = (dir == UP)? --col : (dir == DOWN)? ++col : col;  // 방향이 북쪽이나 남쪽이면 y이동.
 while((wall_ahead(maze,x,y,dir)==0) && (mark[row][col]==0))
 {
  gotoxy(21,8); //확인용
  printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
 
  foward(&x,&y,dir);
  Sleep(1);
  gotoxy(21,7);    //확인용
  printf("-before/after(cnt)=%3d /%3d ",Ecnt,cnt); //확인용
    
  cnt++;
  //Add(&top,x,y,dir);
  if(top >= MAX_STACK_SIZE-1)
  {
   printf("\n  stack overflow.");
   exit(1);
  }
  top++;
  stack[top].row = x;  //스택은 element형 스트럭트.
  stack[top].col = y;
  stack[top].dir = dir;
 
  gotoxy(21,9); //확인용 
  printf("-top=%2d /%2d stack[top]= %2d, %2d ",top,Etop,Estack[Etop].row,Estack[Etop].col); //확인용  
  mark[x][y]=1;
  if(cnt>Ecnt){
   return 0;
  }
  /*if((x==EXIT_ROW)&&(y==EXIT_COL)){
   Etop=top;
   Ecnt=cnt;
   memcpy(Estack,stack,sizeof(Estack));
   for(i=0;i<=top;i++){
    Estack[i].col=stack[i].col;
    Estack[i].row=stack[i].row;
    Estack[i].dir=stack[i].dir;
   return 1;
  }*/
 }

Dirsch(x,y,dir,top,stack,cnt,mark);

return 0;
}

 
 

/********************************************************/
/*    미로찾기 함수.
/********************************************************/
void path_maze(int maze[][MAZE_SIZE],int cnt){ //,element stack[top]){
 element position;
 int x=sx, y=sx, row=x, col=y, dir=UP,i ;  // (현재위치)x, y, (전진할위치)row, col, (방향)dir
 int top=0;

 
 //top의 처음 값 저장.
 Estack[top].row=x;  
 Estack[top].col=y;
 Estack[top].dir=dir;
 gotoxy(x,y+1);  // 첫 걸음 표현.
 printf("＊");  
 cnt++;    // 걸음 카운트 1증가.
 gotoxy(x+1,y+1);
 printf(M_ROBOT); // 생쥐 등장.
 Emark[x][y]=1;
 

 while(still_in_maze(x,y))//쥐가 아직 미로안에 있으면 실행.
 {
  
  if(x==EXIT_ROW && y==EXIT_COL) //탈출 장소 도달시에는 반복문 종료.
   break;
  else{
   i=0;   // UP으로 초기된후 방향을 바꿔주는 횟수.  
   row=x;   // x의 전진방향을 표시할 row.
   col=y;   // y의 전진방향을 표시할 col.
   dir=UP;   // 방향 초기화 UP.
   /* x,y가 전진할 좌표로 row,col 변환.*/
   row = (dir == LEFT) ? --row : (dir == RIGHT)? ++row : row; // 방향이 왼쪽이나 오른쪽이면 x이동.
   col = (dir == UP)? --col : (dir == DOWN)? ++col : col;  // 방향이 북쪽이나 남쪽이면 y이동.
   while(Emark[row][col] || wall_ahead(maze,x,y,dir)) //전진할 곳에 미로나 마크가 벽(1)이면.. 
   {
    Emark[row][col]=1; // 마크 채워줌.
    Sleep(30);  
    right(&dir); // 방향을 바꿈.
    i++;   // 방향 바꾼 횟수++.
    /* row col 방향에 맞추어 다시 수정. */
    row=x;   // row 초기화. 
    col=y;   // col 초기화.    
    row = (dir == LEFT) ? --row : (dir == RIGHT)? ++row : row; // 방향이 왼쪽이나 오른쪽이면 x이동.
    col = (dir == UP)? --col : (dir == DOWN)? ++col : col;  // 방향이 북쪽이나 남쪽이면 y이동.
    gotoxy(21,8); //확인용
    printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
    if( i>3){
     gotoxy(21,9); //확인용 
     printf("-top=%2d stack[top]= %2d,%2d",top,Estack[top].row,Estack[top].col); //확인용
     gotoxy(x+1,y+1);
     printf("＊");
     position=Delete(&top); // pop해준 stack의 [top].
     x=position.row;
     y=position.col;
     gotoxy(x+1, y+1);
     printf(M_ROBOT);
     dir=UP;
     i=0;
    }
    gotoxy(21,8); //확인용
    printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
   }

   while(Emark[row][col]==0 && wall_ahead(maze,x,y,dir)==0){ // 전진위치에 마크가 비었거나 벽이 없으면..
    Add(&top,x,y,dir); // 스택에 현재 좌표 저장.
 
    
    gotoxy(21,9); //확인용 
    printf("-top=%2d stack[top]= %2d,%2d",top,Estack[top].row,Estack[top].col); //확인용
    Sleep(30);
    foward(&x,&y,dir); // 마이크로 마우스 이동.
    cnt++;
    Emark[x][y]=1;  // 현재위치 마크 생성.(1..)
    gotoxy(21,7);    //확인용
    printf("-cnt = %d",cnt); //확인용
    gotoxy(21,8);    //확인용
    printf("-x,y,d: (%2d,%2d,%2d) ",x,y,dir); //확인용
   }   
  }
 }
 Etop=top;
 gotoxy(x+2,y+1); //성공하면...
 printf(SUCCEED); 
}

/********************************************************/
/*   delete함수(스택에서 pop.)
-인자형: top(인덱스).
-리턴값: 스택의 top인덱스의 element형.
/********************************************************/
element Delete(int *top){
 if(top < 0)
 {
  printf(" stack underflower. \n");
  exit(1);
 }
 return Estack[(*top)--];
}

/********************************************************/
/*   Add함수(스택에 push.)
/*   -인자형: top(인덱스), x,y좌표, dir(방향)
/********************************************************/
void Add(int *top,int x,int y,int dir){
 if(*top >= MAX_STACK_SIZE-1)
 {
  printf("\n  stack overflow.");
  exit(1);
 }
 (*top)++;
 Estack[*top].row = x;  //스택은 element형 스트럭트.
 Estack[*top].col = y;
 Estack[*top].dir = dir;
 
}

 

/********************************************************/
/*   벽배치에 따른 중앙벽의 모양을 리턴   */
/*   -인자형: 미로, x,y좌표.
   -리턴값: 1 2 4 8 의 방향값.
/********************************************************/
int get_shape(int m[][MAZE_SIZE],int x,int y){
 
 int s = 0;
 if(m[y][x])
 {
  if(y > 0 && m[y-1][x]) s |= UP;
  if(y < MAZE_SIZE - 2 && m[y+1][x]) s|= DOWN;
  if(x > 0 && m[y][x-1]) s |= LEFT;
  if(x < MAZE_SIZE - 2 && m[y][x+1]) s|= RIGHT;
 }
 return s;
}

/********************************************************/
/*   미로를 화면에 그려주는 함수.    */
/*   -인자형: 미로(배열).
/********************************************************/
void draw_maze(int m[][MAZE_SIZE]){
 int i,j;

 for(j=0; j<MAZE_SIZE; j++)
  for(i=0; i<MAZE_SIZE; i++)
  {
   gotoxy(i+1,j+1);
   print_maze(get_shape(m,i,j));
   
  }
}

/********************************************************/
/*   커서를 x,y좌표로 이동시켜주는 함수.
/********************************************************/
void gotoxy(int x, int y)
{
    COORD Pos = {x*2,y};
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Pos);
}

/********************************************************/
/*   미로의 벽을 출력 하는 함수.
/*   -인자형: int값.
/********************************************************/

void print_maze(int i)
{
 switch(i){
 case 0 : printf("  "); break;
 case 1 : printf("│"); break;
 case 2 : printf("─"); break;
 case 3 : printf("└"); break;
 case 4 : printf("│"); break;  
 case 5 : printf("│"); break;  
 case 6 : printf("┌"); break;
 case 7 : printf("├"); break;
 case 8 : printf("─"); break;
 case 9 : printf("┘"); break;
 case 10 : printf("─"); break;
 case 11 : printf("┴"); break;
 case 12 : printf("┐"); break;
 case 13 : printf("┤"); break;
 case 14 : printf("┬"); break;
 case 15 : printf("┼"); break;
 }
 return;

}

/********************************************************/
/*   생쥐가 출구좌표에 있는지 확인하는 함수. 
/*   -
/********************************************************/
int still_in_maze(int x, int y)  //아직 미로에 들어 있는가?
{   
 if(x>0 && x<MAZE_SIZE-1 && y>0 && y<MAZE_SIZE-1)
  return 1;     // 미로찾기중.
 else
  return 0;     // 탈출성공.
}

/********************************************************/
/*   앞이 막혔는지 뚫렸는지 확인 함수.
/*   -인자형: 미로, x좌표, y좌표, 가리키는 방향.
   -리턴값:
/********************************************************/
int wall_ahead(int m[][MAZE_SIZE], int x, int y, int dir)
{
 x = (dir == LEFT) ? --x : (dir == RIGHT)? ++x : x; // x는 dir이 가리키는 쪽으로 좌나 우로 이동.
 y = (dir == UP)? --y : (dir == DOWN)? ++y : y;  // y는 dir이 가리키는 쪽으로 위나 아래로 이동.
 return m[y][x];          // 즉, 방향이 가리키는 x,y의 자리를 리턴. (maze는 1은 벽, 0은 길이다.)
}

/********************************************************/
/*   생쥐를 앞으로 이동시키는 함수.foward!
/*   -인자형:
/********************************************************/

void foward(int *x, int *y, int dir){
 gotoxy(*x+1,*y+1);
 printf("＊");      // 지나온 길 체크.
 *x = (dir == LEFT) ? --(*x) : (dir == RIGHT)? ++(*x) : *x;
 *y = (dir == UP) ? --(*y) : (dir == DOWN)? ++(*y) : *y;
 gotoxy(*x+1, *y+1);
 printf(M_ROBOT);

 
}
/********************************************************/
/*   방향을 오른쪽으로 돌리는 함수.
/********************************************************/

int right(int *dir)
{
 *dir <<= 1;
 *dir = (*dir > LEFT)? *dir = UP : *dir;
 return *dir;
}

이 글은 스프링노트에서 작성되었습니다.