[Algorithm] stack 이용하여 DFS 구현하기

알고리즘 문제를 풀다보면 DFS 를 이용해야 하는 경우가 매우 많다. 보통은 recursion 을 이용하여 구현하지만 DFS 알고리즘은 stack 자료구조를 이용해서 구현할 수도 있다. 아래는 그 코드이다.

1. Recursion 을 이용한 DFS

void dfs(int x) {
  cout << x << " ";
  visited[x] = true;

  for(int i=0; i<adj[x].size(); i++) {
    int nx = adj[x][i];
    if(visited[nx]) continue;

    dfs(nx);
  }

  return;
}

2. Stack 을 이용한 DFS

void dfs(int x) {
  stack<int> s;

  s.push(x);

  while(!s.empty()) {
    int t = s.top();
    s.pop();

    if(visited[t]) continue;

    visited[t] = true;
    cout << t << " ";

    for(int i=adj[t].size()-1; i>=0; i--) {
      if(visited[adj[t][i]]) continue;
      s.push(adj[t][i]);
    }
  }

  return;
}

🙋‍♂️ BFS 와는 다르게 stack 에 push 하는 순간에 방문 처리를 하지 않고 pop 되는 순간에 방문 처리를 한다. recursion 도 function call 이 stack 구조로 발생함을 생각하고 비교해가며 생각해보자