DFS (다차원 배열)

DFS(Depth First Search)

• 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘

DFS 알고리즘

• BFS 알고리즘에서 큐를 스택으로만 바꾸면 DFS 알고리즘이 된다.
  다른건 다 똑같음!!

1. 시작하는 칸을 "스택"에 넣고 방문했다는 표시를 남김

2. "스택"에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행

3. 해당 칸을 이전에 방문했다면 아무것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입

4. "스택"이 빌 때까지 2번을 반복

• 시간복잡도 : 모든 칸이 스택에 1번씩 들어가므로 칸이 N개일 때 O(N)

BFS vs DFS

• 비록 최종적인 방문 결과는 똑같아도, 방문 순서에서 차이가 있다.

• 거리를 계산할 때는 DFS를 사용할 수 없음. BFS로만 거리계산 가능

  • BFS 의 특징인 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다" 는 성질이 DFS에서는 성립 X

DFS 구현 예시

• 이전에 다루었던 BFS 구현에서, 큐를 스택으로만 바꾼 것 외에는 전부 다 코드가 완전히 일치한다.

#include <bits/stdc++.h>
using namespace std;

int board[502][502] = {...};
bool vis[502][502];

int n= 7, m = 10;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(void)
{
  stack<pair<int,int>> s;
  vis[0][0] = 1;
  s.push({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 x = cur.first + dx[i];
      int y = cur.second + dy[i];
      if(x < 0 || x >= n || y < 0 || y >= m)
        continue;
      if(vis[x][y] || board[x][y] != 1)
        continue;
      vis[x][y] = 1;
      s.push({x,y});
    }
  }
}