[8] 미로 문제 (Maze Problem) _ 스택(Stack)

우선 미로를 표현하기 위해서 1은 막힌 길, 0은 갈 수 있는 길이라고 가정한다. 

n x m 크기의 미로를 표현하기 위해서 2차원 배열을 정의한다.

 

또한 해당 위치에서 다음 위치로 이동할 수 있는 방법은 총 8가지 이다.

위처럼 현재 위치가 [i][j] 라면, 다음으로 이동할 수 있는 곳은 분홍색으로 색칠한 곳이다.

 

따라서 이동할 수 있는 방향을 구조체 배열로 선언할 수 있다.

typedef struct {
    short int vert;
    short int horiz;
}offsets;
 
offsets move[8];
 

다음과 같이 선언한 후

dir (index)	move[dir].vert	move[dir].horiz
0	-1	0
1	-1	1
2	0	1
3	1	1
4	1	0
5	1	-1
6	0	-1
7	-1	-1

위와 같이 move 배열에 저장하면 

현재 위치에서 위로 올라가는 방향부터 시계 방향으로 이동하는 방향을 저장할 수 있다.

 

따라서 현재 위치를 나타내는 [row][col] 에서

다음 위치를 나타내는 [nextRow][nextCol] 을 정의하려면 다음과 같이 정의하면 된다.

nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;

 

미로에서 이동할 때는 

우선 가능한 방향으로 이동하고, 더이상 이동할 수 없으면 되돌아 오는 방법으로 이동한다.

 

따라서 길이 막히면 예전 위치로 되돌아와야하기 때문에 

스택(stack) 자료구조를 이용하면 된다.

 

스택에 담을 원소는 다음과 같이 정의한다.

typedef struct {
    short int row;
    short int col;
    short int dir;
}element;
 

 

C언어 프로그램

입력 파일은 maze.txt이고, 

첫째 줄에는 미로의 크기가, 둘째 줄 부터는 미로가 저장되어 있는 파일이다.

입력의 예시는 다음과 같다.

3 4
0 1 0 0
1 0 1 0
0 0 0 0

또한 미로는 최대 8 x 8 크기라고 가정하였다.

 

미로의 시작은 왼쪽 상단이고, 미로의 끝은 오른쪽 하단이다.

 

출력은 미로의 길이 존재하지 않으면 -1을 출력하고, 

통과할 수 있는 길이면 좌표를 출력하도록 한다.

 

#include <stdio.h>
#include <stdlib.h>
#define N 10 // 미로의 row, col의 최대 개수+2
#define MAX N*N // 스택에 담을 수 있는 최대 개수
 
typedef struct {
    short int vert;
    short int horiz;
}offsets;
offsets move[8]; // 갈 수 있는 8가지 방향에 대한 배열
 
typedef struct {
    short int row;
    short int col;
    short int dir;
}element; // 스택에 담길 원소
 
int top=0;
element stack[MAX];
char maze[N][N];
char mark[N][N] = { 0 };
 
void push(element); // 스택에 원소 push하는 함수
void stackFull(); // 스택이 다 차면 에러 메시지 출력하는 함수
element pop(); // 스택에 원소 pop 하는 함수
 
 
int main() {
    int rowNum, colNum, i,j, found;
    int row, col, nextRow, nextCol, dir;
    FILE* fp;
    element position;
    // input file open, maze의 정보 담는다.
    fp = fopen("maze.txt", "r");
    if (!fp) {
        fprintf(stderr, "file open error\n");
        exit(1);
    }
    fscanf(fp,"%d %d ", &rowNum, &colNum);
    for (i = 1;i <= rowNum;i++) {
        for(j=1;j<=colNum;j++)
            fscanf(fp, "%c ", &maze[i][j]);
    }
 
    // maze의 바깥 부분을 1로 감싸서 갈 수 없는 길로 표시한다.
    for (i = 0;i <= rowNum;i++) {
        maze[i][colNum + 1] = '1';  // maze의 오른쪽
        maze[i][0] = '1'; // 왼쪽
    }
    for (i = 0;i <= colNum + 1;i++) {
        maze[0][i] = '1'; // 위
        maze[rowNum+1][i] = '1'; // 아래
    }
 
    fclose(fp);
 
    //move 배열 만들어줌.(시계방향으로 이동할 수 있도록 함.)
    move[0].vert = -1; move[0].horiz = 0;
    move[1].vert = -1; move[1].horiz = 1;
    move[2].vert = 0; move[2].horiz = 1;
    move[3].vert = 1; move[3].horiz = 1;
    move[4].vert = 1; move[4].horiz = 0;
    move[5].vert = 1; move[5].horiz = -1;
    move[6].vert = 0; move[6].horiz = -1;
    move[7].vert = -1; move[7].horiz = -1;
 
    //initailize
    mark[1][1] = 1;
    stack[0].row = 1;
    stack[0].col = 1;
    stack[0].dir = 2;
    found = 0;
 
    while (top > -1 && !found) { //스택에 원소가 존재하고, 미로 끝까지 도달 못했을 때
        // stack[top] 의 정보를 불러온다.
        position = pop();
        row = position.row; col = position.col;     dir = position.dir;
        while (dir < 8 && !found) { // 가능한 모든 이동 방향으로 이동해보도록 함.
            nextRow = row + move[dir].vert;
            nextCol = col + move[dir].horiz;
            if (nextRow == rowNum && nextCol == colNum) { // 미로 끝에 도달한 경우
                found = 1;
            }
            else if (maze[nextRow][nextCol] == '0' && !mark[nextRow][nextCol]) { // 다음 갈 곳이 갈 수 있는 길이고, 한번도 가보지 않은 경우
                mark[nextRow][nextCol] = 1;
                position.row = row; position.col = col; position.dir = ++dir;
                push(position);
                row = nextRow; col = nextCol; dir = 0; // 다음 갈 곳으로 이동 후 다시 while문 고려
            }
            else 
                ++dir; // 갈 곳이 없는 막힌 길이라면, 그 자리에서 다음 방향을 고려
        }
    }
    if (found) { //미로 끝까지 도달했다면 경로 출력
        printf("The Path is (row, col):");
        for (i = 0;i <= top;i++)    printf("(%d, %d)->", stack[i].row, stack[i].col);
        printf("(%d, %d)->",row, col);
        printf("(%d, %d)\n", nextRow, nextCol);
    }
    else printf("-1");
    system("pause");
    return 0;
}
 
void push(element item) {
    if (top >= MAX - 1)
        stackFull();
    stack[++top] = item;
}
 
void stackFull(){
    fprintf(stderr, "stack is full\n");
    exit(EXIT_FAILURE);
}
 
element pop() {
    if (top == -1)
        return;
    return stack[top--];
}