[바킹독의 실전 알고리즘] 0x0A강 -DFS

DFS(Depth First Search)

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

예시

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

=> 모든 칸이 스택에 1번씩 들어감

-> 시간복잡도는 칸이 N개일 때 O(N)

(0, 0)과 상하좌우로 이어진 모든 파란칸 확인
(0, 0)에 방문했다는 표시 + 해당 칸 -> 스택에 넣음

스택이 빌 때까지 스택의 top을 빼고 해당 좌표의 상하좌우를 살펴보면서 스택에 넣어주는 작업 반복

step 1
스택의 top: (0, 0) -> pop 
(0, 0)과 상하좌우로 인접한 (0, 1)과 (1, 0) 모두 파란 칸 -> 아직 방문 X
=> 2개의 칸에 방문했다는 표시 + 큐에 넣음

step 2
스택의 top: (1, 0) -> pop
(1, 0)과 상하좌우로 인접한 (2, 0) -> 아직 방문 X
=> (2, 0)에 방문했다는 표시 + 큐에 넣음

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

#define X first
#define Y 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} }; 
 
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){
  ios::sync_with_stdio(0);
  cin.tie(0);
  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.X << ", " << cur.Y << ") -> ";
    
    for(int dir = 0; dir < 4; dir++){ 
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir]; 
      
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(vis[nx][ny] || board[nx][ny] != 1) continue; 
      vis[nx][ny] = 1; 
      S.push({nx,ny});
    }
  }
}

BFS vs DFS

방문 순서에 큰 차이

BFS
상하좌우로 퍼져나감, 거리 순으로 방문
현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다 -> DFS에서 성립 X
=> 거리 계산 시 DFS 사용 X
-> 다차원 배열에서 (순회하는 문제에서) BFS 사용

Flood Fill: BFS / DFS 
거리 측정: BFS
그래프, 트리: DFS

---