[Fundamentals of Data Structures in c++] 미로찾기 DFS 구현

DFS로 구현한 미로 찾기 알고리즘

1. DFS란?

Depth First Search 의 약자로, 한 길로 갈 수 있는 길의 끝까지 간 다음, 막다른 길이면 한걸음 후퇴하고 다음 길을 찾는 알고리즘 입니다.

링크 : https://en.wikipedia.org/wiki/Depth-first_search

2. DFS 알고리즘 개요

1.  이 알고리즘은 Stack 자료구조를 사용합니다.
2.  방위 중 우선 자신이 제일 먼저 갈 수 있는 길로 갑니다. 그리고 이전의 길을 스택에 Push 합니다.
3.  그 길에서 2를 반복합니다. 
4. 막다른 길을 만났을 경우, 스택의 Top으로 돌아갑니다. Top 위치에는 다른 길로 갈 수 있을 수 있습니다.
5. 또 2를 반복 합니다. 중요한 점은, 이미 갔던 길은 다시 갈 수 없다는 것입니다.

3. offset 및 Items의 개요

move[]는 N~NW까지 8개 방위의 값을 나타냅니다.

Items 구조체는 스택에 저장할 자료형 입니다. x, y 인덱스 정보와 방향을 담고 있습니다.

struct offset {
          int a, b; 
} move[8] = { -1,0 , -1,1, 0,1, 1,1 , 1,0 , 1,-1, 0,-1, -1,-1 };
struct Items {
           Items(int xx = 0, int yy = 0, int dd = 0) : x(xx), y(yy), dir(dd) {}
           int x, y, dir;
  
};

4. 미로를 탐색하는 SearchMaze 함수 소스코드

 void SearchMaze(const int m, const int p) {
  mark[1][1] = 1;
  stack stack;
  Items temp(1, 1, E);
  stack.push(temp);
  // 방문한 노드의 개수를담을 변수 선언.
  int visitedCount = 0;
  // 스택이 비어있지 않을 동안 루프 돌림.
  while (!stack.empty()) {
   // 현재 스택의 Top을 기준으로 미로 탐색 실시.
   temp = stack.top();
   stack.pop();
   int i = temp.x;
   int j = temp.y;
   int d = temp.dir;
   // temp의 d의 정보에 따라 while 루프를 돌리는 횟수가 달라짐.
   while (d < 8) {
    // d(방향)에 따른 좌표 변화를 담을 변수 g, h 선언.
    int g = i + ::move[d].a;
    int h = j + ::move[d].b;
    // 탐색한 방향이 출구라면, 출력.
    if ((g == m) && (h == p)) {
     // 출력 코드.
     return;

    }
    // 다음 인덱스의 미로를 갈 수 있고, 한번도 가본적이 없는 곳이라면,
    if ((!::maze[g][h]) && (!::mark[g][h])) {
     // 마킹 실시 후 i,j,d 의 정보를 다음 인덱스로 초기화 시킴으로써 DFS 실시.
     mark[g][h] = 1;
     temp.x = i;
     temp.y = j;
     temp.dir = d + 1;
     stack.push(temp);
     i = g;
     j = h;
     d = N; // d를 N(=0)으로초기화 시킴으로서 다음 인덱스에서 8방향 전부 탐색을 가능하게 함 .

    }
    // 다음 인덱스로 갈 수 없다면, 다음방향을 탐색한다.
    else d++;

   }

  }
  // 스택이 비어서 다음방향으로 이동할 수 없을 경우, 미로엔 길이 없음을 출력.
  cout << "미로를 탈출할 수 없습니다." << endl;


 }