다차원 배열이 주어졌을 때 stack을 이용하여 DFS 구현하기 : C++

dfs의 경우 재귀로 풀 수도 있고 스택을 이용해서 풀 수도 있지만 이번에는 스택을 이용해 푸는 방법에 대해 알아보려고 한다. 사실 재귀를 이용해서 푸는 것이 코드가 더 간결하다. 구조적으로 재귀를 쓰는 것 자체가 컴퓨터 내에서 스택을 쓰는 것과 마찬가지이기 때문에 다음에 재귀를 이용해서 푸는 방법에 대해서도 다뤄보도록 하겠다.

#include <iostream>
#include <stack>
#include <utility>
using namespace std;

int main(void){
    ios:: sync_with_stdio(0);
    cin.tie(0);

    int arr[100][100] = 
    { {1,1,1,0,1,0,0,0,0,0},
    {1,0,0,0,1,0,0,0,0,0},
    {1,1,1,0,1,0,0,0,0,0},
    {1,1,0,0,1,0,0,0,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0} };

    bool isVisited[100][100];

    pair<int, int> dir[4] = {
        pair<int, int>(-1, 0),
        pair<int, int>(1, 0),
        pair<int, int>(0, -1),
        pair<int, int>(0, 1)
    };

    int n = 7, m = 10;

    stack<pair<int, int> > s;

    isVisited[0][0] = 1;
    s.push(pair<int, int>(0, 0));

    while(!s.empty()){
        pair<int, int> cur = s.top();
        s.pop();

        cout << "(" << cur.first << "," << cur.second << ") -> ";

        for(int i = 0; i < 4; i++){
            int adjX = cur.first + dir[i].first;
            int adjY = cur.second + dir[i].second;

            if(adjX < 0 || adjX >= n || adjY < 0 || adjY >= m) continue;
            if (isVisited[adjX][adjY] == true || arr[adjX][adjY] == 0) continue;

            isVisited[adjX][adjY] = true;
            s.push(pair<int, int>(adjX, adjY));
        }
    }
    cout << "end" << "\n";
}

선언과 초기화

---

• line 10 ~ 17 : 다차원 배열을 선언한다. (주어진 다차원 배열을 저장한다.)
• line 19 : 각 칸의 방문 여부를 확인하기 위해 다차원 배열과 같은 크기의 배열을 선언한다.
• line 21 ~ 26 : 22줄부터 순서대로 배열의 상, 하, 좌, 우 좌표를 구할 방향 좌표이다.
• line 28 : 각 칸의 좌표를 담을 pair 형 stack을 선언한다.

탐색 과정

---

• line 32 : 시작점인 (0,0)을 방문했다고 명시한다. 시작점은 들어오는 다차원 배열에 따라 다르다.

• line 33 : stack에 시작점인 (0,0)을 삽입한다.

• line 35 : stack에 남은 노드가 없을 때까지 반복한다.
• line 36 ~ 37 : stack의 가장 top에 있는 노드를 확인한다.
• line 39 : 탐색 과정을 출력한다.
• line 41 : 해당 칸의 상하좌우로 인접한 칸을 탐색한다.
• line 45 : 탐색하는 칸이 범위 밖일 경우 탐색하지 않는다.
• line 46 : 인접한 칸이 이미 방문했던 칸이거나 빈 칸이라면 탐색하지 않는다.
• line 47 ~ 48 : 방문한 칸을 명시하고 stack에 방문한 칸을 삽입한다.