깊이 우선 탐색 / DFS

DFS(Depth First Search)

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. 넓게 탐색하는 것이 아닌 깊게 탐색하는 방법이다. 
각각의 좌표가 시작 좌표에서 떨어진 거리를 알 수 있었던 bfs와 달리 dfs는 거리 측정이 힘들다. 그래서 배열에서 탐색을 하는 문제에선 주로 BFS를 사용하여 문제를 푼다. 그렇다고 DFS가 아예 안쓰이는 것은 아니니 잘 이해하고 넘어가는게 좋다.

 

DFS 구현 이론

큐를 사용하는 BFS와 달리 DFS는 스택을 사용하여 구현한다. BFS에서 사용한 예시인 파란칸 찾기 문제를 예시로 대략적인 플로우를 살펴보자.

• 시작 좌표 방문 표시 후, 스택에 push
• 스택의 top값을 pop하고 해당 좌표에 접해있는 상,하,좌,우 좌표를 확인
• 인접 좌표 중에서 파란칸이면서 방문한 적 없는 좌표가 있으면 방문 표시 후, 스택에 push
• 2,3번 과정을 반복
• 스택이 비면 탐색 종료.

---

DFS 구현 코드

BFS 구현 코드에서 큐를 스택으로 바꾼거말고는 큰 차이가 없다. 해당 코드가 이해가 안된다면 앞서있는 bfs 게시물을 보고오면 도움이 조금은 될 것이다.

#include <iostream>
#include <stack>
#include <utility>
using namespace std;

int board[100][100];    //1은 파란칸, 0은 빨간칸
bool vis[100][100];   //방문 여부 확인용 배열

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};     //상하좌우 표시용

int main(){
    stack<pair<int,int> > S;
    vis[0][0]=1;  //시작점 방문 표시
    S.push(make_pair(0,0));  //큐에 시작점 push

    while (!S.empty())
    {
        pair<int, int> cur = S.top();     //현위치 저장 후 큐에서 삭제
        Q.pop();
        
        for(int dir=0 ; dir<4 ; dir++ ){
            //현위치 주변 상하좌우 좌표 확인
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            //범위 밖일 경우 확인
            if(nx < 0 || nx >= 100 || ny < 0 || ny >= 100){
                continue;   //loop의 끝으로 이동
            }
            //이미 방문 했거나 빨간 칸인 경우 확인
            if(vis[nx][ny] || board[nx][ny]!=1){
                continue;
            }
            vis[nx][ny] = 1;
            S.push(make_pair(nx,ny));   //조건에 맞는 좌표 방문 표시 후, 삽입
        }
    }
    
}