[실전 알고리즘] 0x0A강

[실전 알고리즘] 0x0A강 - DFS

2022. 2. 2. 18:41ㆍAlgorithm/4강

1. 알고리즘 설명

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

2. 예시

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

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

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

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

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

사실상 BFS에서 큐가 스택으로 바뀐 것이다.

큐 - BFS

스택 - DFS

DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. BFS와 DFS는 방문 결과는 똑같지만 방문 순서에서 큰 차이가 있다.

DFS 구현 예시

아래 코드는 바킹독이 구현한 DFS인데 이전 BFS와 비교하면 큐만 스택으로 바뀐 것을 확인할 수 있다.

#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});
    }
  }
}

3. BFS vs DFS

BFS는 큐를 쓰고 DFS는 스택을 쓴다는 차이가 있지만 원소 하나를 빼내고 주변을 살펴본다는 알고리즘의 흐름은 똑같다. 하지만 둘의 방문 순서는 큰 차이가 있다. BFS의 경우, 상하좌우로 퍼져나가는 것을 볼 수 있다. 그리고 이전에서 다룬 BFS의 성질인 거리 순으로 방문한다는 것 또한 잘 성립한다. DFS의 경우, 한 방향으로 막힐 때 까지 쭉 직진을 한다.

BFS에서 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 따라서 다차원 배열에서 굳이 BFS 대신 DFS를 써야하는 일이 없다. Flood Fill은 BFS와 DFS 중에서 어느 것을 써도 상관없지만 거리 측정은 BFS만 할 수 있으니 굳이 BFS 대신 DFS를 쓸 일이 없다. 앞으로 다차원 배열에서 순회하는 문제를 풀 때는 BFS로 짜는 것을 권장한다. 하지만 나중에 그래프와 트리라는 자료구조를 배울 때 DFS가 필요하게 된다. 그러니 여기서는 DFS는 스택을 써서 다차원 배열의 순회를 처리하는 알고리즘이고, 깊이를 우선해서 탐색한다 정도로만 기억하고 넘어가면 된다.

참고자료