[CS]깊이 우선 탐색(DFS = Depth First Search)

DFS : 깊이 우선 탐색

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• Brute Force(완전 탐색) 알고리즘
• 스택 or 재귀를 이용해 구현
• 임의 노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법
  

DFS의 효용성

• 일반적인 상황에서 DFS는 BFS의 기능으로 모두 대체 가능
• 일반적인 상황에서 트리의 높이를 리턴하는 BFS의 특성상 BFS가 DFS보다 유용하다.
• 단, 그래프와 트리에서 DFS가 유용해진다.

DFS <-> BFS

• 다차원 배열에서 DFS가 스택으로 구현된 경우 적용 가능
• 스택을 큐로 바꾸면 BFS가 된다.
• DFS 구현 방법
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택 상단 노드에 방문하지 않은 인접 노드가 있으면, 그 노드를 스택에 넣고 방문 처리
  3. 방문하지 않은 인접 도느가 없다면, 스택에서 최 상단 노드를 꺼냄
  4. 2번 과정을 더이상 수행할 수 없을 때까지 반복

DFS 사용 예제

1. 그래프 DFS 사용 예제

#include <iostream>
#include <vector>
using namespace std;

bool visited[9]; // 전역으로 선언하면 모두 false로 초기화
vector<int> graph[9]; // 벡터 자체가 9개 

// DFS 함수 정의
void dfs(int start) {
    // 현재 노드를 방문 처리
    visited[start] = true;
	
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for (int i = 0; i < graph[start].size(); i++) {
        int x = graph[start][i]; 
        if (!visited[x])
			dfs(x);
    }
}

int main(void) {
    // 노드 1에 연결된 노드 정보 저장 
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);
    
    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);
    
    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);
    
    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);
    
    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);
    
    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);
    
    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);
    
    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);
    
    dfs(1);
}

2. 재귀 DFS 사용 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 20
int dist[100001] = {0};
bool visited[100001];   //방문 체크 행렬
//DFS에 사용되는 자료구조
bool arr[MAX][MAX];     //1. 인접행렬
vector<int> list[MAX];  //2. 인접 리스트
vector<pair<int, int>> edges;   //3. 간선 리스트
void dfs(int x, int n){
    visited[x] = true;
    for(int i = 1; i <= n; ++i)
		//x, i가 연결되어 있고, i를 가보지 않은 경우
        if(arr[x][i] == true && visited[i] == false)
            dfs(i, n);
}

3. 스택 DFS 사용 예제

#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 visited[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>> Q;

  visited[0][0] = 1; // (0, 0)을 방문했다고 명시

  Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.

  while(!Q.empty()){
    pair<int,int> cur = Q.front(); 
		Q.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(visited[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우 넘어감

      visited[nx][ny] = 1; // (nx, ny)를 방문했다고 표시

      Q.push({nx,ny});
    }
  }
}