[자료구조] Chapter3. STACKS AND QUEUES(2)

※ 이 카테고리의 글들은 knu EK.Ryu 교수님의 <자료구조> 수업을 듣고 나름대로 필자가 정리한 글입니다.

※ 부족한 설명이 있거나, 잘못 알고 작성한 부분이 보인다면 댓글로 알려주시면 감사하겠습니다😊

3.5 A Mazing Problem

미로(maze)는 오랫동안 흥미 있는 문제였습니다. 실험 심리학자들은 쥐가 미로에서 음식을 찾도록 훈련시켜 왔고, 많은 추리 작가들은 영국식 정원 미로를 살인 사건의 배경으로 이용했습니다.

미로는 스택의 좋은 응용이 되므로 우리도 이 문제에 대해 관심을 가져 봅시다. 이 절에서는 미로를 찾아내는 프로그램을 구현했습니다. 프로그램은 미로에서 올바른 길을 찾을 때까지 잘못된 경로를 여러 번 취하나, 일단 올바른 길을 찾은 후에는 잘못된 경로를 거치지 않고 곧바로 미로를 빠져나갈 수 있습니다.

 

Maze: representation

프로그램 작성 시 제일 먼저 해야 할 일은 미로를 표현하는 것입니다.

미로를 표현하는 가장 쉬운 방법은 막힌 길을 1로, 통과할 수 있는 길을 0으로 한 2차원 배열을 이용하는 것입니다.

<그림1. 예제 미로>

 

이러한 2차원 배열로 표현된 미로에서 미로 속의 쥐는 행과 열로 언제든지 그 위치를 표현할 수 있습니다. 만약 X가 현재의 위치, maze[row][col]을 나타낸다면 아래의 그림2는 이 위치에서 이동 가능한 8개의 인접 위치를 보여줍니다. 이 여덟 방향을 N, NE, E, SE, S, SW, W, NW로 명세할 수 있습니다.

<그림2. 가능한 이동>

 

다만, 모든 위치가 8개의 인접 위치를 가지고 있는 것은 아닙니다. 만일 [row][col]이 미로의 가장자리, 즉 경계선에 있게 되면 여덟 방향이 아닌 오직 세 방향만 있을 수 있습니다. 이러한 경계 조건의 특이성을 피하기 위해서는 미로의 주위를 1로 둘러쌈으로써 해결 할 수 있습니다.

<그림3. 경계선에서 가능한 이동>

 

<그림4. 경계를 1로 둘러싼 미로>

 

 

그러면 m * p 미로는 (m+2) * (p+2) 배열이 필요하게 되는데 이 때, 미로의 입구는 [1][1]이 되고, 출구는 [m][p]가 됩니다.

이제 이동할 방향들을 아래의 그림5와 같이 배열 move에 미리 정의할 수 있습니다.

<그림5. 이동 테이블>

 

여기서 8개의 가능한 이동 방향은 0에서 7까지의 숫자로 나타내고, 각 방향에 대해서는 수평과 수직 좌표의 오프셋으로 나타냅니다. 이 테이블을 만들기 위한 C 선언문은 다음과 같습니다.

typedef struct {
	short int vert;
    short int horiz;
} offsets;
offsets move[8]; // 각 방향에 대한 이동 배열

 

이 상황에서 현재의 위치를 maze[row][col]이라 하면, 다음 이동할 위치 maze[nextRow][nextCol]은 다음과 같이 설정됩니다.

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

 

미로를 이동할 때에는 여러 방향의 선택이 있을 수 있습니다. 이때 어떤 방향이 최상의 선택일지 알 수 없으므로, 현재의 위치를 지정하고 선택할 수 있는 한 방향을 선택해야 합니다. 이렇게 현재의 위치를 지정하면 만약 잘못된 길로 가더라도 되돌아와서 다른 방향을 시도할 수 있습니다. (stack)

먼저 북쪽에서 시작하여 시계 방향으로 순서대로 가능한 방향을 검사하고, 한 번 시도했던 길을 다시 시도하지 않기 위해 시도했던 길을 배열 mark에 기록하여 유지할 수 있습니다.

배열 mark는 0으로 초기화하고, maze[row][col]을 방문하게 되면 mark[row][col]을 1로 변경합니다.

이제 미로 알고리즘 코드를 작성해봅시다.

 

미로 탐색 함수 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define MAZE_SIZE 10
#define EXIT_ROW 8
#define EXIT_COL 8

// 스택에 저장될 위치 정보를 담은 구조체
typedef struct {
    int row;    // 현재 행 위치
    int col;    // 현재 열 위치
    int dir;    // 이동 방향
} element;

// 이동 방향을 정의한 구조체 (vert는 수직 이동, horiz는 수평 이동)
typedef struct {
    int vert;   // 수직 방향
    int horiz;  // 수평 방향
} offsets;

// 스택과 관련된 변수들
element stack[100];   // 스택 배열
int top;              // 스택의 최상위 인덱스

// 8방향으로의 이동을 정의
offsets move[8] = {
    {-1, 0},  // 북쪽
    {-1, 1},  // 북동쪽
    {0, 1},   // 동쪽
    {1, 1},   // 남동쪽
    {1, 0},   // 남쪽
    {1, -1},  // 남서쪽
    {0, -1},  // 서쪽
    {-1, -1}  // 북서쪽
};

// 미로와 방문 여부를 나타내는 배열
int maze[MAZE_SIZE][MAZE_SIZE] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
    {1, 1, 1, 0, 1, 1, 0, 0, 0, 1},
    {1, 1, 1, 0, 0, 0, 0, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 1, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int mark[MAZE_SIZE][MAZE_SIZE];  // 방문 여부를 기록하는 배열

// 스택에서 요소를 꺼내오는 함수 (pop)
element pop(int* top) {
    if (*top == -1) {
        printf("Stack is empty!\n");
        element dummy = { -1, -1, -1 }; // 빈 값 반환
        return dummy;
    }
    else {
        return stack[(*top)--]; // 스택에서 요소를 꺼내서 반환
    }
}

// 스택에 요소를 넣는 함수 (push)
void push(element item) {
    stack[++top] = item;  // 스택에 요소를 추가
}

// 경로를 탐색하는 함수 (이미 주어진 함수)
void path(void) {
    int i, row, col, next_row, next_col, dir, found = FALSE;
    element position;

    // 출발점(1,1)을 방문했다고 표시하고 스택에 저장
    mark[1][1] = 1;
    top = 0; // 스택의 최상단을 0으로 설정
    stack[0].row = 1;
    stack[0].col = 1;
    stack[0].dir = 1;

    // 스택이 비어 있지 않고 출구를 찾지 못한 경우 계속 탐색
    while (top > -1 && !found) {
        // 스택에서 현재 위치를 꺼내옴
        position = pop(&top);
        row = position.row;
        col = position.col;
        dir = position.dir;

        // 8방향 탐색을 시작
        while (dir < 8 && !found) {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;

            // 출구에 도착한 경우
            if (next_row == EXIT_ROW && next_col == EXIT_COL)
                found = TRUE; // 출구를 찾았다고 표시
            else if (!maze[next_row][next_col] && !mark[next_row][next_col]) {
                // 방문하지 않은 경로라면
                mark[next_row][next_col] = 1; // 방문했다고 표시

                // 현재 위치를 스택에 저장
                position.row = row;
                position.col = col;
                position.dir = ++dir; // 다음 방향을 스택에 저장
                push(position);

                // 새 위치로 이동
                row = next_row;
                col = next_col;
                dir = 0; // 새로운 위치에서 8방향 탐색을 다시 시작
            }
            else {
                ++dir; // 이동할 수 없으면 다음 방향으로 전환
            }
        }
    }

    // 경로를 찾은 경우
    if (found) {
        printf("The path is:\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("The maze does not have a path\n");
}

// 메인 함수
int main() {
    // mark 배열 초기화 (0으로 모든 칸을 방문하지 않은 상태로 설정)
    for (int i = 0; i < MAZE_SIZE; i++)
        for (int j = 0; j < MAZE_SIZE; j++)
            mark[i][j] = 0;

    // 미로 경로 탐색 시작
    path();

    return 0;
}

 

path 분석: 미로의 크기가 함수 path의 연산 시간을 결정합니다. 미로의 각 위치는 한 번만 방문되므로 최악의 경우 연산 시간은 O(m*p)입니다. 여기서 m과 p는 각각 미로의 행과 열입니다.

---

3.6 Evaluation of Expressions

수식을 표기하는 표준 방식은 두 피연산자 사이에 이항 연산자가 위치하는 중위 표기법(infix notation)입니다.

(말이 거창하지 1 + 3, a // b 와 같은 표현)

이 중위 표기법은 수식을 쓰는 데 있어서 가장 보편적이지만 수식을 계산하는 컴파일러에서는 그렇지 않습니다. 컴파일러는 일반적으로 괄호를 사용하지 않는 후위 표기법(posifix notation)을 사용합니다. 이 표기법에서는 연산자가 피연산자 이후에 오는데, 이해를 돕기 위해 아래의 중위 표기법과 후위 표기법을 비교한 표를 봅시다.

<그림6. 중위 표기법과 후위 표기법>

 

후위 표기식의 연산

중위 표기를 후위 표기로 변환하는 함수를 작성하기 전에, 후위 표기식을 쉽게 연산하는 방법을 먼저 다뤄봅시다.