[알고리즘] C++ 스택과 재귀와 DFS

본 포스팅은 인프런 [Do it! 알고리즘 코딩테스트 With C++]을 수강한 뒤 복습 용도로 작성하는 글이다.

그렇기에 자세한 강의를 원한다면 ↓

https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%94%A8%EC%81%A0%EC%81%A0/dashboard

[지금 무료]Do it! 알고리즘 코딩테스트 with C++ 강의 | 하루코딩 - 인프런

 

1. 스택

LIFO (Last In, First Out): 말그대로 나중에 들어온게 먼저 나간다라는 의미

 

 

2 → 1 순으로 들어왔으면 나갈때는 1 → 2 순으로 나간다. 이때, 스택에서 나중에 들어온 값이 Top이 된다. (가장 위의 값)

c++에서의 사용법

#include <stack>
stack<int> s;

s.push(10);       // 값 넣기
s.push(20);
s.top();          // 맨 위 값 확인 (20)
s.pop();          // 맨 위 값 제거 (20 제거)
s.empty();        // 비었는지 확인 (true/false)
s.size();         // 크기

 

 

 

2. DFS(깊이 우선 탐색)

DFS는 깊이 우선 탐색이라 가장 깊은 노드까지 먼저 탐색한 후, 더 이상 못 가면 백트래킹해서 다른 길을 탐색하는 알고리즘이다.

1 → 2 → 4 이후 더 이상 갈 곳이 없기 때문에 2로 돌아간 후, 5를 탐색한다.

이후 다시 갈 곳이 없기 때문에 2로 돌아오고, 이제는 더 탐색할 곳이 없기때문에 1로 돌아가서 다음 경로를 탐색한다.

 

한마디로, "더 깊이 파고들다 막히면 돌아가기"

 

이러한 DFS는 앞서 말했듯이 스택으로 구현하거나, 혹은 재귀로 구현 가능하다.

그래서 스택과 재귀, DFS는 비슷한 구조를 갖는다고 말한다.

 

재귀의 구조

A {
	A {
    		A {
			.....
            			} //먼저 종료
                    			}
                        			} //가장 나중 종료

 

만약 A라는 재귀함수가 있다고 할 때 A()를 호출하면, 그 안에서 또 A()가 호출되고, 또 그 안에서 A()가 호출된다.

이렇게 어떤 조건을 갖추거나 연산이 끝날 때까지 자기 자신을 호출하고, 특정 조건 달성 시 호출이 끝나는 것이 재귀함수이다.

그러나 이전의 A()를 호출한 이후 그 안의 A()가 호출되었다고 해서, 이전의 A()가 끝이 난 것이 아니다.
끝날 때는 가장 나중에 실행되었던(가장 안 쪽에 있던) A()부터 끝이 나면서 가장 처음에 실행되었던 A()가 가장 나중에 끝난다.

즉, 스택의 가장 나중에 들어온 값이 가장 먼저 나가는 LIFO의 구조를 가지고 있는 것이다.

 

다시 DFS로 돌아와서,
DFS에서 LIFO의 구조를 사용하는 이유는,

위의 사진과 같은 상황이라고 할 때, 먼저 1이 들어가고, 탐색을 끝낸다.

그리고 그 다음 노드인 2,3이 들어가고, 가장 위의 노드인 2(현재 상황에서, 3이 가장 위가 될수도 있다.)의 탐색을 끝낸다.

그리고 DFS 깊이 우선 탐색이기 때문에 2의 차례가 끝났으면 다음 노드들인 4,5가 들어간다.

 

그 다음, 가장 Top에 있는 5 노드의 탐색을 하고, 갈 곳이 없기 때문에 돌아와 4의 탐색을 한 뒤, 마찬가지로 갈 곳이 없기때문에 최종적으로 3으로 돌아가게 되고,

 

3의 다음 노드들인 6,7이 들어가고 다시 7 → 6 순으로 탐색을 하고, 종료하게 된다.

 

위 방법 처럼 DFS를 구현할 수 있으므로, 스택 또는 재귀를 활용하는 것이다.

 

---

 

재귀로 구현한 DFS

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next, graph, visited);
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {},          // 0번 노드는 사용 안 함
        {2, 3},      // 1번 노드: 2, 3과 연결
        {1, 4},
        {1},
        {2}
    };
    vector<bool> visited(5, false);

    dfs(1, graph, visited); // 1번 노드에서 시작
}

스택으로 구현한 DFS

void dfs_stack(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int node = st.top(); st.pop();

        if (visited[node]) continue;
        visited[node] = true;
        cout << node << " ";

        // 인접 노드들을 스택에 push (역순으로 넣으면 같은 결과)
        for (int i = graph[node].size() - 1; i >= 0; i--) {
            int next = graph[node][i];
            if (!visited[next]) {
                st.push(next);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {},          // 0번 노드는 사용 안 함
        {2, 3},      // 1번 노드: 2, 3과 연결
        {1, 4},
        {1},
        {2}
    };
    vector<bool> visited(5, false);

    dfs_stack(1, graph, visited); // 1번 노드에서 시작
}

 

스택 구현 DFS에서 스택에 push하는 부분에서 역순으로 인접 노드를 push한 이유는
스택은 LIFO이기 때문에 인접 노드를 역순으로 넣으면 정방향 순서로 탐색이 가능해서이다.
위의 예시 그림에서도 봤듯이 1→{2,3}일 때, 3부터 push하고 2를 push해야지 2가 먼저 pop되어 탐색이 된다.
즉, 재귀 DFS와 같은 방문 순서를 만들고 싶다면 역순 push를 해야한다. 
반드시 역순으로 push해야하는건 아니지만, 순서를 보장해야할 때는 필수다!

 

---

결론!

• DFS는 원래 스택 기반 알고리즘
• 다만 재귀가 내부적으로 스택을 쓰기 때문에, 재귀로 구현하는게 더 편함
• 하지만 재귀 제한이 있거나, 스택 직접 구현이 필요한 경우엔 stack을 사용해서 DFS를 구현해야함

 

 

큐와 BFS는 다음 포스팅에서 이어서,,