define FALSE 0

define TRUE 1

include

include

include

//enum 선언을 통해 방향을 구분한다. typedef enum direction{u,r,d,l,e}Direction;

//현재 위치와 이동방향을 저장하는 구조체를 선언하 typedef struct Pos { int x; int y; Direction direction; }Pos;

//pop할 노드의 원소로 typedef struct StackNode { Pos pos;//선언한다 struct StackNode* pLink;//포인터 형식이다 }StackNode;

typedef struct LinkedStype { int cur;//현재 원소개수 StackNode* ptop;//top노드 처리 }LinkedStack;

LinkedStack*createLinkedStack() { LinkedStack pStack=NULL; int i=0; pStack=(LinkedStack)malloc(sizeof(LinkedStack)); memset(pStack,0,sizeof(LinkedStack)); return pStack; }

void push(LinkedStack* pStack, StackNode element) { int ret=FALSE; StackNode*pNode=NULL; if(pStack != NULL) { pNode=(StackNode*)malloc(sizeof(StackNode)); if(pNode!=NULL) { *pNode = element; pNode->pLink=pStack->ptop; pStack->ptop =pNode; ret=TRUE; } else{ printf("오류,push()\n"); } } else { printf("오류,push()\n");

}
return ret;}

StackNode*pop(LinkedStack*pStack) { StackNode*pNode=NULL; if(pStack!=NULL) { pNode=(StackNode*)malloc(sizeof(StackNode)); if(pNode!=NULL) { pNode=pStack->ptop; pStack->ptop=pNode->pLink; } else {printf("오류,pop()\n");}

}
else
{
    printf("오류, pop()");
}

return pNode;}

int isLinkedStackFull(LinkedStack*pStack) { int ret =FALSE; return ret; }

int isLinkedStackEmpty(LinkedStack*pStack) { int ret= FALSE; if(pStack!=NULL) { if(pStack->cur==0) ret =TRUE; } else{printf("오류. isLinkedStackEmpty()\n");} return ret; }

void displayLinkedStack(LinkedStack *pStack) { StackNode*pNode=NULL; if(pStack!=NULL) { pNode=pStack->ptop; while(pNode!=NULL) { printf("%c",pNode->pos); pNode=pNode->pLink;

    }}
else
    {printf("오류");
}

printf("\n"); } int **vi;//방문함수

//미로찾기 행렬의 크기 할당하는 함수 //방문여부를 확인하는 매트릭스도 같이 메모리를 할당 int** getMazeSize(int row, int col) { int i,j; int** maze; //메모리할당 maze=(int*)malloc(sizeof(int)row); vi=(int)malloc(sizeof(int)row); for(i=0;i<col;i++) { maze[i]=(int)malloc(sizeof(int)col); vi[i]=(int)malloc(sizeof(int)*col); }

//방문매트릭스 값 초기화
for(i=0;i<row;i++)
{
    for(j=0;j<col;j++)
    {
        vi[i][j]=0;

    }
}
return maze;

}

//미로찾기 행렬의 값 초기화 void getMaze(int** maze, int i, int j, int value) { maze[i][j]=value; }

//기존의 방향에 길이 없으면 위, 오른쪽 아래, 왼쪽 순으로 돌아가면서 방향값을 얻는다 Direction getNextDirection(StackNode element) { switch(element.pos.direction) { case u:return r; case r:return d; case d: return l; case l: return e; } }

//이동할 방향의 위치값을 얻어내는 함수이다 StackNode getNextPosition(StackNode element) { switch(element.pos.direction) { case u:element.pos.x--; return element; case r:element.pos.y++; return element; case d:element.pos.x++; return element; case l:element.pos.y--; return element; case e:return element; } }

//실직적으로 미로를 찾는 함수이다 int findPath(int** maze,StackNode element,LinkedStack *pStack,int endX, int endY) { int ret;//미로찾기의 성공여부 확인하는 값 int nextX,nextY;//다음 위치값 StackNode nextDirection,*pNode;

//미로에서 이동은 시계방향이며문(위,오,아,왼) 각 방향별로 길이 없으면 순사대로 길이 있는지 찾아가는 for문 for(;element.pos.direction !=e;element.pos.direction = getNextDirection(element)) { nextDirection = getNextPosition(element);//이동할 방향의 위치값을 얻어낸 nextX=nextDirection.pos.x;//이동할 방향의 위치X nextY=nextDirection.pos.y;//이동할 방향의 위치Y

//x인덱스의 크기                y인덱스의 크기            방문하지 않은 위치여야 하며    뚫린길이어야 한다
if((7>=nextX&&nextX>=0)&&(7>=nextY&&nextY>=0)&&vi[nextX][nextY]==0&&maze[nextX][nextY]==0)
{
    if(nextX==endX&&nextY==endY)//만약에 출구라면
    {
        vi[element.pos.x][element.pos.y]=1;
        push(pStack,element);//지금위치와
        push(pStack,nextDirection);//다음이동할 출구위치를 스택에 저장하고
            return ret = TRUE;//출구를 찾았으니 TRUE값을 반환한다.
    }
    //다음방향이 이동가능하다면
    vi[element.pos.x][element.pos.y]=1;//현재위치를 방문했다고 표시하고
    push(pStack,element);//스택에 넣고
    nextDirection.pos.direction = u;//다음위치에서 시작할 방향은 up부터 이므로 up으로 초기화한후
    return findPath(maze,nextDirection,pStack,endX,endY);//다음 위치로 넘어간다
}

} //만약 어느 방향으로도 갈수 없다면 if(element.pos.direction==e&&!isLinkedStackEmpty(pStack)) { vi[element.pos.x][element.pos.y]=1; pNode = pop(pStack);//이전위치로 돌아가서 return findPath(maze,*pNode,pStack,endX,endY);//다른길을 찾는다. } else { return ret = FALSE;//만약 스택이 empty다, 즉 길이 없다면 false 반환 }

void startFindPath(int** maze,int endX, int endY) { int ret; LinkedStack* pStack; StackNode Node; Node.pos.x=1; Node.pos.y=1; Node.pos.direction=u; pStack = createLinkedStack(); ret=findPath(maze,Node,pStack,endX,endY); //반환된 ret값을 통해 성공 실패 여부를 출력한다 if(ret) { printf("미로찾기성공 \n"); displayLinkedStack(pStack);//성공했다면 path를 출력한다 } else{printf("미로찾기실패 \n");} } } int main() { int row,col,value,i,j; int** maze; FILE* stream; stream=fopen("maze.txt","r"); fscanf(stream,"%d %d",&row,&col); maze=getMazeSize(row,col); i=0; j=0; for(i=0;i<row;i++) { for(j=0;j<col;j++) { fscanf(stream,"%d",&value); getMaze(maze,i,j,value); } } //현재 미로값이 잘 저장되어 있는지 확인해본다. for(i=0;i<row;i++) { for(j=0;j<col;j++) { printf("%d",maze[i][j]);

    }
    printf("\n");
}

//출구까지 길이 있는지 확인한다. startFindPath(maze,9,9); fclose(stream); return 0; }