[DS] A Maze Problem (스택으로 미로 문제 풀기)

# A Maze Problem

- 목표: 입구로부터 출구까지의 경로를 찾음

- 조건: 0은 지나갈 수 있고, 1은 지나갈 수 없음. 직진이나 대각선 방향으로 이동이 가능

> 한 개의 프로그램은 한 개의 미로 경로를 탐색

> 현재 위치에서 이동 가능한 모든 방향 (북쪽부터 시작 → 시계방향으로 이동) 대하여

이동 가능 여부 판단

> 처음 발견한 이동 방향으로 마우스의 좌표를 수정

> 이동 가능한 방향이 없을 경우, 이전 위치로 되돌아감

> 스택을 이용하여 이동했던 위치를 기록하고 이전 위치로 찾아감.

만일 백 트랙을 시도했으나 스택이 비어있다면 결과는 실패

 

 

# 미로 찾기 스택 구현

- 구현: 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 pop하여 이전 단계까지 돌아옴

 

 

# 미로 문제의 특성

- a*b 미로는 (a+2)*(b+2) 배열이 필요 → 위 아래, 양 옆에 벽이 존재하기 때문

- 입구의 위치: [1][1]

- 출구의 위치: [a][b]

- 방문했던 위치가 아닐 경우 미로는 8방향을 탐색할 수 있음

 

 

# 미로 알고리즘

1. 현재 위치에서 이동 가능한 방향을 탐색

1.1 대각선 위치로 이동이 가능하므로 북쪽 방향부터 시계 방향으로 탐색함

1.2 탐색한 방향의 좌표가 이동 가능하고, 이전에 방문한 노드가 아니라면 이동

  > 현재 좌표와 이동할 방향 정보를 스택에 push, 현재 좌표를 이동한 방향의 좌표로 업데이트

  > 이동한 위치에 방문 표시

2. 이동 가능한 방향이 없다면, 이동 가능 조건(방문하지 않았으며 0인 경로)을 만족할 때까지 백트래킹

  > 탐색 재개 위치를 찾을 수 없다면, 즉 스택이 비어있다면 경로가 없는 것이므로 중단

3. 이동 가능한 방향의 좌표가 출구 위치라면 탐색을 중단하고, 스택에 쌓여있는 정보를 모두 pop하여 출력 (출구에서 입구로 향하는 경로 순으로 출력)

 

[semi pseudo code]

void path (void) { // 경로가 있다면 패스 출력
    mark[1][1] = 1; // 방문 설정(시작점)
    top = 0; // 시작점 스택에 push
    stack[0].row = 1; // 현재 위치 스택에 저장
    stack[0].col = 1;
    stack[0].dir = 1;
    while (top > -1 && !found) { // stack에 path가 남아있고 출구를 찾지 못한 상태
        position = pop(&top);
        row = position.row; col = position.col; dir = position.dir;
        while(dir < 8 && !found) // 내 주변의 8방향을 찾아보기               
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(next_row == EXIT_ROW && next_col == EXIT_COL) // 다음 위치가 EXIT이면
            {
                found=TRUE; // 탈출 성공
            }
            else if(!maze[next_row][next_col] && !mark[next_row][next_col])
            /* 다음 위치가 0이면서 방문한적이 없을 때*/
            {
                mark[next_row][next_col] = 1;
                position.row = row; position.col = col; position.dir = ++dir;
                push(&top, position); // 현재 위치 스택에 저장
                row = next_row; col = next_col; dir = 0;
            }
            else ++dir; // exit이 아니며 갈 수 없는 곳일 때 (방문을 했거나 벽이거나)
        }
    }

    if ( found ) { // 출구 찾음
        printf("path found");
    }
    else printf("no path found"); // 미로 탈출 못함
}

* 벽인 부분을 미리 1로 설정해 두는 방법도 있음 !

 

 

# 미로 알고리즘 구현

[코드]

#include <stdio.h>
#define MAX_STACK_SIZE 100
#define FALSE 0
#define TRUE 1
#define EXIT_ROW 11
#define EXIT_COL 15

typedef struct {
    int vert; // 수직 좌표
    int horiz; // 수평 좌표
} offsets;
offsets move[8]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};/*방향 표시*/

typedef struct {
    short int row;
    short int col;
    short int dir;
} element;
element stack[MAX_STACK_SIZE];

void path (void);
void push(int *top, element position);
element pop(int* top);

int top;

int maze[13][17] = {
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
        {1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1},
        {1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1},
        {1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1},
        {1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1},
        {1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1},
        {1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
        {1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1},
        {1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int mark[13][17] = { 0, };

int main(){
    path();
    return 0;

}

void path (void) { // 경로가 있다면 패스 출력
    int i, row, col, next_row, next_col, dir;
    int found = FALSE; // 1이면 출구
    element position;
    mark[1][1] = 1; // 방문 설정(시작점)
    top = 0; // 시작점 스택에 push
    stack[0].row = 1; stack[0].col = 1; stack[0].dir = 1;
    while (top > -1 && !found) { // stack에 path가 남아있고 출구를 찾지 못한 상태
        position = pop(&top); // 스택에서 pop
        row = position.row; col = position.col; dir = position.dir;
        while(dir < 8 && !found) // 내 주변의 8방향을 찾아보기
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(next_row == EXIT_ROW && next_col == EXIT_COL) // 다음 위치가 EXIT이면
            {
                found=TRUE; // 탈출 성공
            }
            else if(!maze[next_row][next_col] && !mark[next_row][next_col]) // 다음위치가 0이면서 방문한적이 없을 때
            {
                mark[next_row][next_col] = TRUE;
                position.row = row; position.col = col; position.dir = ++dir;
                push(&top, position); // 스택에 현재 위치 저장
                row = next_row;
                col = next_col;
                dir = 0;
            }
            else ++dir;  // exit이 아니며 갈 수 없는 곳일 때 (방문을 했었거나 벽이거나)
        }
    }

    if ( found ) { // 출구 찾음
        printf("< Path >\n"); // 방문한 길 출력
        printf("row col\n");
        for ( i = 0; i <= top; i++ )
            printf("%2d%5d\n", stack[i].row, stack[i].col);
        printf("%2d%5d\n", row, col);
        printf("%2d%5d\n", EXIT_ROW, EXIT_COL);
    }
    else printf("no path found!!\n"); // 미로 탈출 X
}

void push(int *top, element position)     
{
    (*top)++;
    stack[*top].row = position.row;
    stack[*top].col = position.col;
    stack[*top].dir = position.dir;
}

element pop(int* top)                   
{
    element result;
    if(*top<0){
        printf("Stack is Empty.\n");
    }
    else{
        result = stack[*top];
        (*top)--;
    }
    return result;
}

 

[실행결과]

 

 

 

 

 

---

[참고]

#21 [C 자료구조] 스택으로 미로 문제 풀기