[바킹독 알고리즘] 0x0A강:DFS in 다차원 배열

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

그래프에서 DFS 예제

0,0 부터 시작해 방문했다는 표시를 남긴다.

0,0 과 상하좌우 인접한 칸에 방문했다는 표시를 남기고 stack에 좌표를 담는다.

stack의 top을 pop하고 top의 인접한 상하좌우를 탐색한다.

사진만으로 이해가 어렵다면 바킹독 알고리즘 영상을 직접 보면 이해가 더욱 쉬울 것이다.

정리

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

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

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

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

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

DFS 구현 코드

#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} }; // 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; 
  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는 동심원을 그리는거처럼 인접한 좌표들을 방문하지만, DFS는 한 좌표에 깊이 끝까지 방문한 뒤 다음 좌표의 깊이 끝까지 방문하는것과 비슷하다. 

BFS에서는 현재에서 인접한 칸은 현재보다 거리가 1만큼 떨어져있다는 성질이 적용되지만, DFS에서는 이 성질이 성립되지 않음을 알 수 있다. 이처럼 BFS와 DFS는 차이가 존재하기에 거리와 관련된 문제를 풀 때는 BFS로 푸는게 더 알맞다.