[자료구조] 스택의 응용 - 미로 탐색

스택(Stack)의 응용 - 미로 탐색

---

미로 탐색 문제

• 미로에 갇힌 주인공이 출구를 찾는 문제

• 미로가 서로 연결된 여러 개의 방 또는 칸으로 구성되어 있다고 가정

출구를 찾는 과정

• 기본적인 방법은 시행착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도

  • 이 때, 현재의 경로가 안 될 경우에 다른 경로를 선택해야 하므로 다른 경로들이 어딘가에 저장되어 있어야 함

  • 현재 위치에서 가능한 경로 중에서 가장 가까운 경로를 저장해야 유리함

  • 가장 최근에 저장한 경로가 쉽게 추출되도록 스택을 사용

• 현재 위치에서 갈 수 있는 방들의 좌표를 스택에 저장한 후 막다른 길을 만나면 아직 가보지 않은 방 중에서 가장 가까운 방으로 다시 돌아가서 새로운 경로를 찾는다

• 한 번 지니간 방을 다시 가지 않도록 각 방들을 지나갈 때 마다 방문했다고 표시를 해야 함

  • 하나의 스택을 가정

  • 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장한다고 가정

  • 스택에서 맨 위의 위치를 꺼내어 현재 위치로 사용하여 같은 작업을 반복

    • 현재의 위치가 출구와 같거나 모든 위치를 다 검사해 볼 때까지 계속

• 의사 코드

  maze_search():
  
  스택 s과 출구의 위치 x, 현재 생쥐의 위치를 초기화
  while (현재의 위치가 출구가 아니면) do
    현재 위치를 방문한 것으로 표기
    if (현재위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈 수 있다면)
        then 그 위치들을 스택에 push
    if (is_empty(s))
        then 실패
    else 스택에서 하나의 위치를 꺼내어 현재 위치로 설정
  성공;

프로그램으로 구현

• 미로를 어떤 식으로 표현할 것 인가?

  • 2차원 배열을 이용하여 표현 ex) maze[][]

  • 배열의 값이 0이면 갈 수 있는 길을 의미

  • 배열의 값이 1이면 지나갈 수 없는 벽을 의미

• 현재 위치는 m으로 표시, 출구는 x로 표시

  • 위치는 (행, 열)의 좌표값으로 표시

    • 따라서 스택에 저장되는 데이터는 (행, 열) 좌표가 되어야 한다

  • 방문이 끝난 위치는 maze 배열의 값을 '.'으로 바꾸어 다른 위치들과 구별

• 스택에 비었는데도 출구를 찾지 못했다면 미로 탐색에 실패

• 동일한 좌표값이 중복해서 스택에 저장되어도 문제는 발생하지 않음

  • 어떤 위치가 방문이 되면 그 주위의 위치들이 모두 방문된 것으로 표시가 되므로 다음에 동일한 위치가 스택에서 꺼내지더라도 다시 방문하지 않음

• C Program

    #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 data[MAX_STACK_SIZE];
        int top;
    } StackType;
  
    // 스택 초기화 함수
    void init_stack(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)) {
            fprintf(stderr, "스택 포화 에러\n");
            return;
        }
        else s->data[++(s->top)] = item;
    }
    // 삭제함수
    element pop(StackType *s)
    {
        if (is_empty(s)) {
            fprintf(stderr, "스택 공백 에러\n");
            exit(1);
        }
        else return s->data[(s->top)--];
    }
    // 피크함수
    element peek(StackType *s)
    {
        if (is_empty(s)) {
            fprintf(stderr, "스택 공백 에러\n");
            exit(1);
        }
        else return s->data[s->top];
    }
    // ===== 스택 코드의 끝 ===== 
  
    element here = { 1,0 }, entry = { 1,0 }; // 현재 위치와 entry point(진입 좌표)
  
    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) {
        if (r < 0 || c < 0) return;
        if (maze[r][c] != '1' && maze[r][c] != '.') {
            element temp = {r, c};
            push(s, temp);
        }
    }
  
    void maze_print(char maze[MAZE_SIZE][MAZE_SIZE]) {
        printf("\n");
        for (int i = 0; i < MAZE_SIZE; i++) {
            for (int j = 0; j < MAZE_SIZE; j++) {
                printf("%c", maze[i][j]);
            }
            printf("\n");
        }
    }
  
    int main(void) {
        int r, c;
        StackType s;
  
        init_stack(&s);
        here = entry;
        while (maze[here.r][here.c] != 'x') {
            r = here.r;
            c = here.c;
            maze[r][c] = '.';
            maze_print(maze);
            push_loc(&s, r - 1, c);
            push_loc(&s, r + 1, c);
            push_loc(&s, r, c - 1);
            push_loc(&s, r, c + 1);
            if (is_empty(&s)) {
                printf("failure\n");
                return 0;
            }
            else {
                here = pop(&s);
            }
        }
        printf("Success\n");
        return 0;
    }

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)