DFS

DFS(Depth First Search)

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

DFS 과정

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때 까지 2번을 반복

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

 

DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. 최종적인 방문 결과는 똑같더라도, 방문 순서에서 아주 큰 차이가 있다.

(0,0) 에서 시작해 상하좌우로 이어진 모든 파란색 칸을 확인해보자.

(0,0) 에 방문했다는 표시를 남기고 해당 칸을 스택에 넣는다. 이게 초기의 세팅이고 이후에는 스택이 빌 때 까지 계속 스택의 top을 빼고 해당 좌표의 상하좌우를 살펴보면서 스택에 넣어주는 작업을 반복하면 된다.

지금 스택의 top은 (0,0)이었고 pop을 한다. 그리고 (0,0)의 상하좌우 칸을 보는데, 이중에서 파란색 칸이면서 방문하지 않은 칸을 찾는다.

(0, 1)과 (1, 0)이 모두 파란 칸이면서 아직 방문하지 않은 칸이니 방문했다는 표시를 남기고 스택에 넣는다.

지금 스택의 top은 (1, 0)이고 pop을 한다. 상하좌우 칸들을 확인해보면 (0, 0)은 파란 칸이지만 이미 방문을 했고, (1, 1)은 빨간 칸이다. 유일하게 (2, 0)만 파란색 칸이면서 아직 방문하지 않은 칸이니까 (2, 0)에 방문했다는 표시를 남기고 스택에 넣는다.

BFS와 마찬가지로 이 과정을 반복하면 파란색 칸들을 전부 방문할 수 있다.

DFS 구현 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502] =
{{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} }; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  stack<pair<int,int> > S;
  vis[0][0] = 1; // (0, 0)을 방문했다고 명시
  S.push({0,0}); // 스택에 시작점인 (0, 0)을 삽입.
  while(!S.empty()){
    pair<int,int> cur = S.top(); S.pop();
    cout << '(' << cur.X << ", " << cur.Y << ") -> ";
    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
      if(vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
      S.push({nx,ny});
    }
  }
}

DFS vs BFS

BFS는 큐를 쓰고 DFS는 스택을 쓴다는 차이점과 방문 순서에 큰 차이가 있다.

BFS의 시작점을 중간으로 잡았는데, 동심원과 같이 상하좌우로 퍼저나가는 것을 알 수 있다. BFS의 성질인 거리 순으로 방문한다는 것 또한 성립함을 알 수 있다. DFS의 방문 순서는 한 방향으로 막힐 때까지 쭉 직진을 한다는 것을 알 수 있다. 

 

또한 BFS에서 사용했던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 거리가 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. (0,0)에서 DFS를 시작할 때 나오는 상황인데, 빨간색 칸은 거리가 4인 반면 검정색 칸은 거리가 3이다.

그래서 거리를 계산할 때는 DFS를 사용할 수 없다. 굳이 다차원 배열에서 BFS대신 DFS를 써야하는 일이 없다.

-> 거리 측정은 BFS만 가능. BFS대신 DFS를 쓸 일이 없다. 다차원 배열에서 순회하는 문제를 풀 때 계속 BFS만 짜게 된다. DFS는 트리라는 자료구조에서 사용된다. 

 

출처 : 바킹독님 블로그 https://blog.encrypted.gg/942