스택 예제: 미로찾기

스택

스택은 데이터를 쌓는다. 그리고 가장 나중에 들어온 데이터를 먼저 처리한다. 당장 눈에 들어온 일부터 먼저 처리하는 느낌이다. 미로를 탐험하다보면 보고 있는 위치가 어떤 장소이냐에 따라 스택에 넣을 지 말지, 탐색을 할 지를 결정할 수 있다.

 

위치

struct Pos {
    int row;
    int col;

    // 디버깅을 위한 편의 기능
    friend ostream &operator<<(ostream &os, const Pos &pos) {
        cout << "(" << pos.row << ", " << pos.col << ")" << flush;
        return os;
    }
};

 

스택으로 미로찾기

void StackMaze() {
    Stack<Pos> s;

    Pos start = {1, 1}; // i = 1, j = 1  시작 지점

    s.Push(start);

    while (!s.IsEmpty()) {
        Pos p = s.Top();
        s.Pop();

        const char mark = maze[p.row][p.col];

        if (mark == 'G') {
            cout << "Found!" << endl;
            break;
        }

        if (mark != '1' && mark != 'X') {
            maze[p.row][p.col] = 'X';
            s.Push({p.row + 1, p.col});
            s.Push({p.row - 1, p.col});
            s.Push({p.row, p.col + 1});
            s.Push({p.row, p.col - 1});
        }
    }
}

 

재귀호출

스택이 반복문과 조건식으로 탐색의 진행여부를 결정한다면 재귀호출은 조건식으로 탐색 여부를 결정한다.

재귀호출로 미로찾기

int RecurMaze(Pos p) {

    const char mark = maze[p.row][p.col]; // 상수화 및 고정
    // 해당지점의 표시를 먼저 확인한다
    // 'G'인 경우 종료
    if (mark == 'G') {
        cout << "Found!" << endl;
        return 1;
    }
    // 'G'가 아닌 경우
    // '1'인 경우 : return
    // 'x'인 경우 : return
    // 'o'인 경우 : x 표시하고 다른 방향으로 이동

    if (mark != '1' && mark != 'X') {
        maze[p.row][p.col] = 'X';

        if (RecurMaze({p.row + 1, p.col}))
            return 1;
        if (RecurMaze({p.row - 1, p.col}))
            return 1;
        if (RecurMaze({p.row, p.col + 1}))
            return 1;
        if (RecurMaze({p.row, p.col - 1}))
            return 1;
    }
    return 0;
}