바킹독의 실전 알고리즘 : DFS

바킹독의 실전 알고리즘 : DFS

DFS : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선순위로
BFS : 다차원 배열에서 각 칸을 방문할 때 너비를 우선순위로

DFS 방법

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

-> 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 O(n)

구현

구현은 내가 일단 시도해보자.

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second 

int board[502][502]; // 0,1로 정의된 배열 
vool 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와의 차이

이미지 연상으로 기억하는 게 좋을 것 같다. BFS는 상하좌우로 동심원 생기듯이 방문한다면, DFS는 일단 직진해서 한 방향 파고 그다음 방향 파듯이 방문한다.

또한, "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다"는 BFS 성질이 DFS에서는 성립하지 않는다. 거리 측정은 BFS만이 가능하니 웬만하면 BFS로 푸는 것이 좋다(DFS는 추후에 그래프와 트리 자료구조에서 나온다)