[자료구조] 미로찾기 maze / 스택

스택을 이용한 미로찾기

스택 s과 출구의 위치 x, 현재 생쥐의 위치를 초기화 ;
while( 현재의 위치가 출구가 아니면 )
{     현재위치를 방문한 것으로 표기
      if( 현재 위치의 상하좌우 위치 중 아직 방문되지 않았고 갈수 있는 길이 있으면 )
       그 위치들을 모두 스택 s에 push(순서는 관계 없음);
  if( is_empty(s) ) 실패;
      else 스택 s에서 하나의 위치를 꺼내어 현재 위치로 만든다;
}
성공;

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100
#define MAZE_SIZE 10

typedef struct Mouse
{
    short x;
    short y;
}Mouse;

typedef struct Stack
{
    Mouse data[MAX_SIZE];
    int top;
}Stack;

char maze[MAZE_SIZE][MAZE_SIZE]={
    {'1','1','1','1','1','1','1','1','1','1'},
    {'m','0','0','0','1','0','0','0','0','1'},
    {'1','0','0','0','1','0','0','1','0','1'},
    {'1','0','1','1','1','0','0','1','0','1'},
    {'1','0','0','0','1','0','0','1','0','1'},
    {'1','0','1','0','1','0','0','1','0','1'},
    {'1','0','1','0','1','0','0','1','0','1'},
    {'1','0','1','0','1','0','0','1','0','1'},
    {'1','0','1','0','0','0','0','1','0','X'},
    {'1','1','1','1','1','1','1','1','1','1'}};

void init(Stack *p)
{
    p->top=-1;
}

int is_full(Stack *p)
{
    return ( p->top == MAX_SIZE-1);
}

int is_empty(Stack *p)
{
    return (p->top == -1);
}

void push(Stack *p, Mouse data)
{
    if(is_full(p))
    {
        printf("스택이 꽉찼습니다\n"); return ;
    }
    else
    {
        p->top++;
        p->data[p->top].x=data.x;
        p->data[p->top].y=data.y;
    }
}

Mouse pop(Stack *p)
{
    if(is_empty(p))
    {
        printf("스택이 비어있습니다\n");
        exit(1);
    }
    
    return p->data[(p->top)--];
}

void FindWay(Stack *s,int x,int y)
{
    if(x < 0 || y < 0 || x > MAZE_SIZE || y > MAZE_SIZE) return ;
    
    if(maze[x][y] != '1' && maze[x][y] != '.')
    {
        Mouse tmp;
        tmp.x=x;
        tmp.y=y;
        
        push(s,tmp);
    }
}

int main()
{
    Stack s;
    Mouse m;
    int i, j, x, y;
    
    init(&s);
    
    // 시작점 탐색
    for(i=0;i<MAZE_SIZE;i++)
    {
        for(j=0;j<MAZE_SIZE;j++)
        {
            if(maze[i][j]=='m')
            {
                m.x=i;
                m.y=j;
            }
        }
    }
    
    printf("미로 \n"); 
    for(int i=0; i<MAZE_SIZE; i++){
        for(int j=0; j<MAZE_SIZE; j++){
            if(maze[i][j]=='0'){
                printf("◻︎");
            }else if(maze[i][j]=='1'){
               printf("◼︎");
            }else {
                printf("%c",maze[i][j]);
            }
        }
        printf("\n");
    }

    printf("\n이동 경로\n");
    printf("시작 (%d,%d) -> ",m.x,m.y);
    
    while(maze[m.x][m.y] != 'X')
    {
        x=m.x;
        y=m.y;
        
        maze[x][y]='.'; // 방문한 곳을 표시
        
        // 이동 가능한 곳을 탐색
        FindWay(&s,x+1,y);
        FindWay(&s,x-1,y);
        FindWay(&s,x,y+1);
        FindWay(&s,x,y-1);
        
        if(is_empty(&s))
        {
            printf("이동경로를 찾을 수 없습니다. 실패 \n");
            return 0;
        }
        else
        {
            m=pop(&s); // 현재 좌표를 변경
            printf("(%d,%d) -> ",m.x,m.y);
        }
    }
    printf("도착\n");
    printf("탐색 성공\n");
    
    return 0;
}

 

출력

미로 
◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎
m◻︎◻︎◻︎◼︎◻︎◻︎◻︎◻︎◼︎
◼︎◻︎◻︎◻︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◼︎◼︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◻︎◻︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◼︎◻︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◼︎◻︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◼︎◻︎◼︎◻︎◻︎◼︎◻︎◼︎
◼︎◻︎◼︎◻︎◻︎◻︎◻︎◼︎◻︎X
◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎◼︎

이동 경로
시작 (1,0) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (2,2) -> (2,1) -> (3,1) -> (4,1) -> (4,2) -> (4,3) -> (5,3) -> (6,3) -> (7,3) -> (8,3) -> (8,4) -> (8,5) -> (8,6) -> (7,6) -> (7,5) -> (6,5) -> (6,6) -> (5,6) -> (5,5) -> (4,5) -> (4,6) -> (3,6) -> (3,5) -> (2,5) -> (2,6) -> (1,6) -> (1,5) -> (1,7) -> (1,8) -> (2,8) -> (3,8) -> (4,8) -> (5,8) -> (6,8) -> (7,8) -> (8,8) -> (8,9) -> 도착
탐색 성공