[Data Structure] #2-7 스택을 이용한 미로 탐색

스택을 이용한 미로 탐색

미로 탐색시에는 어떤 자료구조를 사용하는 것이 좋을까? (사실 이미 답을 알지만..) 미로 탐색의 특징을 생각해보자. 미로를 탐색할 때 길이 막힌 경우에는 왔던 길을 되돌아갈 수 있어야 한다. 되돌아가야 한다는 점이 중요하다. 마지막으로 거쳤던 좌표를 다시 알아내야 한다는 점이다. 이러한 특징은 스택의 마지막에 넣은 값이 가장 먼저 나오는 점과 동일하다. 이것 하나 때문에 스택을 쓰는 것이다.

 생각보다 코드는 간단하다.

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

#define MAX_STACK_SIZE 100
#define MAZE_SIZE 6

// 좌표를 저장하기 위한 구조체
typedef struct {
    short r;
    short c;
} element;

typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

void init(StackType *s){
    s->top = -1;
}

int is_empty(StackType *s){
    return s->top == -1;
}

int is_full(StackType *s){
    return s->top == MAX_STACK_SIZE-1;
}

void push(StackType *s, element item){
    if (is_full(s)) {
        exit(1);
    }
    s->stack[++(s->top)] = item;
}

element pop(StackType *s){
    if (is_empty(s)) {
        exit(1);
    }
    return s->stack[(s->top)--];
}

element peek(StackType *s){
    if (is_empty(s)) {
        exit(1);
    }
    return s->stack[s->top];
}

element here = {1,0};
element entry = {1,0};

char maze[MAZE_SIZE][MAZE_SIZE] = {
    {'1','1','1','1','1','1'},
    {'e','0','1','0','0','1'},
    {'1','0','0','0','1','1'},
    {'1','0','1','0','1','1'},
    {'1','0','1','0','0','x'},
    {'1','1','1','1','1','1'}
};

void push_loc(StackType *s, int r, int c){
    // 배열 범위를 벗어난 r,c는 금지한다.
    if (r < 0 || c < 0 || r > MAZE_SIZE || c > MAZE_SIZE) return;
    // 벽(1)이 아니고, 이미 왔던 곳(.)이 아니다 = 갈 수 있다
    if (maze[r][c] != '1' && maze[r][c] != '.') {
        element tmp;
        tmp.r = r;
        tmp.c = c;
        push(s, tmp);
    }
}

void print(){
    int i, j;
    for (i=0; i<MAZE_SIZE; i++) {
        for (j=0; j<MAZE_SIZE; j++) {
            printf("%c",maze[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int r,c;
    StackType s;

    init(&s);
    here = entry; // entry는 이때 한번만 사용된다
    while (maze[here.r][here.c] != 'x') {
        r = here.r;
        c = here.c;
        maze[r][c] = '.';
        
        print();
        printf("------------\n");
        
        // 스택은 가장 마지막에 넣은 것을 가장 먼저 뽑아준다
        // 그러므로 북-남-서-동 순서로 넣으면
        // 동-서-남-북 의 순서로 나오게 된다
        push_loc(&s, r-1, c); // north
        push_loc(&s, r+1, c); // south
        push_loc(&s, r, c-1); // west
        push_loc(&s, r, c+1); // east
        
        if (is_empty(&s)) {
            printf("실패\n");
            exit(1);
        }else{
            here = pop(&s);
        }
    }
    printf("성공\n");
    return 0;
}

 생각보다 심플하다. 핵심은 매번 Stack에서 가장 최근의 좌표값을 얻어낸다는 점이다. 그리고 그 좌표의 동서남북을 살펴보고 비어있으면 다시 넣는다. 스택에 넣을 때는 북남서동의 순서로 넣는다. 그래야 꺼낼 때 동서남북의 순서로 꺼낸다. 이 순서는 반드시 있어야 하는 것은 아니다. 입맛대로 정하면 된다.