[Algorithm] DFS 알고리즘 (Depth First Search)

깊이 우선탐색 (DFS)란?

DFS는 그래프 전체를 탐색하는 방법중 하나로써 시작점 부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법입니다. 스택이나 재귀함수를 통해서 구현할 수 있는데 재귀함수가 구현이 간편하기에 대부분 재귀함수로 구현하는것 같습니다. 구현시 주의할점은 노드를 방문시 방문 여부를 반드시 검사해야합니다. 그렇지 않다면 무한루프에 빠질 수 있습니다.
[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

 

DFS의 장점

1. 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
2. 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있음
3. 구현이 너비 우선 탐색(BFS) 보다 간단함

 

DFS의 단점

1. 단순 검색 속도는 너비 우선 탐색(BFS) 보다 느림 
2. 해가 없는 경우에 빠질 가능성이 있음

(사전에 임의의 깊이를 지정한 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색하도록 함) 
3. 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없음

(목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음)

 간단한 DFS 구현 (C / C++)

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1050;
int n,m;
vector<int> v[MAX];
bool check_dfs[MAX];

//DFS Search
void DFS(int index){
  check_dfs[index] = true; //정점 방문 체크
  printf("%d ",index); //방문한 정점 출력
  
  for(int i=0;i<v[index].size();i++){ 
    int next = v[index][i];
    
    if(!check_dfs[next]){ //방문하지 않았다면 DFS() 호출
      DFS(next);
    }
  }
}

int main() {

  scanf("%d %d",&n,&m);
  
  //그래프 노드관계 입력
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    
    v[a].push_back(b);
    v[b].push_back(a);
  }
  
  DFS(0);

  return 0;
}