DataStructure - Stack 응용2

4. 미로 탐색 문제

4.1 미로 탐색 방법

• 모든 위치는 (행, 열)로 표시
• 입구 위치를 스택에 넣어주면 탐색이 시작 됨
• 현재 스택에는 입구 위치만 들어 있음
• 스택이 공백상태가 아닌 동안 스택에서 하나의 위치를 꺼내 현재 위치로 만든다(만약 공백 상태가 되면 미로를 빠져나갈 수 없음) ?
• 만약 현재 위치 (r,c)가 출구이면 탐색은 성공적으로 끝남
• 그렇지 않으면 현재 위치에서 이웃인 위쪽과 아래쪽, 왼쪽과 오른쪽 위치를 살펴봄
• 만약 방문하지 않았고 갈 수 있는 위치이면 그 위치들을 모두 스택에 삽입 함

4.2 미로 탐색 알고리즘

searchExit()

스택 s와 출구의 위치 x를 초기화;
s에 입구의 위치를 삽입;
while(e.isEmpty() = false)
do 현재 위치 <- s.pop();
   if(현재 위치가 출구 위치이면)
   	 then 성공;
   if(현재 위치의 위, 아래, 왼쪽, 오른쪽 위치가 아직 방문되지 않았고 갈 수 있으면)
     then 그 위치들을 스택 s에 push();
실패;

4.3 미로 탐색을 위한 2차원 좌표 클래스

// 파일이름 : Location2D.h
struct Location2D{
  int row; // 현재 위치의 행 번호
  int col; // 현재 위치의 열 번호
  Location2D (int r=0, int c=0) {row = r; col=c;}
  // 위치 p가 자신의 이웃인지를 검사하는 함수
  bool isNeighbor(Location2D &p){
    return ((row == p.row && (col == p.col-1 || col==p.col+1)) || (col == p.col &&(row == p.row-1 || row == p.row+1)));
  }
  // 위치 p가 자신과 같은 위치인지를 검사하는 함수(연산자 오버로딩 사용)
  bool operator==(Location2D &p) { return row == p.row && col == p.col;}

};

4.4 STL을 이용한 미로 탐색 프로그램 구현

• 코드

#include "Location2D.h" // 위치 클래스 포함
#include <stdio.h>
#include <stack> // STL의 stack 탬플릿 파일 포함

using namespace std;
const int MAZE_SIZE = 6; // 미로 맵 크기 고정
char map[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'}
};

// (r,c)가 갈 수 있는 위치인지를 검사하는 함수
// (r,c)가 배열 안에 있고, 값이 갈 수 있는 위치 '0'이거나 출구 'x'이어야 함
bool isValidLoc(int r, int c){
  if(r<0 || c<0 || r>=MAZE_SIZE || c>=MAZE_SIZE) return false;
  else return map[r][c] =='0' || map[r][c] == 'x';
}

// 미로 탐색 프로그램 함수
int main(){
  stack<Location2D> locStack; // 위치 스택 객체 생성
  Location2D entry(1,0); // 입구 객체
  locStack.push(entry); // 스택에 입구 위치 삽입

  while(locStack.empty() == false){ // 스택이 비어 있지 않는 동안
    Location2D here = locStack.top(); // 스택에 상단 객체 복사
    locStack.pop();

    int r = here.row;
    int c = here.col;

    printf("(%d, %d)\n",r,c); // 현재 위치를 화면에 출력
    if(map[r][c] == 'x'){ // 출구이면 -> 탐색 성공
      printf("Maze Search Success\n");
      return 0;
    }else{ // 출구가 아니면 현재 위치를
      map[r][c]='.'; // 현재 위치를 지나옴으로 처리
      if(isValidLoc(r-1,c)) locStack.push(Location2D(r-1,c));
      if(isValidLoc(r+1,c)) locStack.push(Location2D(r+1,c));
      if(isValidLoc(r,c-1)) locStack.push(Location2D(r,c-1));
      if(isValidLoc(r,c+1)) locStack.push(Location2D(r,c+1));
    }
  }
  printf("Maze Search Fail\n"); // 스택이 공백 상태가 되면 출구 탐색이 실패함
  return 0;
}

• 실행결과
  

참고문헌

천인국·최영규 지음, 『c++로 쉽게 풀어쓴 자료구조』, 생능출판(2016), p.124~