깊이 우선 탐색 ( DFS )

깊이 우선 탐색 ( DFS )

• 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘
• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운
  갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.

 

깊이 우선 탐색 특징

• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것
• 스택(Stack)을 사용
  - 사실 스택을 사용하지 않아도 구현이 가능하다. 왜냐하면 컴퓨터는 구조적으로 항상 스택의 원리를
    사용하기 때문이다.
• 자기 자신을 호출하는 재귀 알고리즘의 형태이다.
• 탐색 과정이 시작 노드에서 한없이 깊게 진행되는 걸 막기 위해 깊이 제한(depth bound)을 사용
• 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 돌아온다.
  -> 이 과정을 백트래킹(backtracking)이라고 한다.

깊이 우선 탐색 장점과 단점

< 장점 > 

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음

< 단점 >

• 해가 없는 경로에 깊이 빠질 가능성 존재.
  -> 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법
       이 유용할 수 있음
• 얻어진 해가 최단 경로가 된다는 보장이 없음.
  -> 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 
       이때 얻어진 해는 최적이 아닐 수 있다.

 

깊이 우선 탐색을 사용하는 경우

• 모든 노드를 방문하고자 하는 경우 사용

 

동작 방식

DFS는 다음과 같은 간단한 알고리즘에 따라서 동작한다.

1. 스택의 최상단 노드를 확인합니다.
2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면    =>   그 노드를 스택에 넣고 방문처리합니다.
                                       방문하지 않은 인접 노드가 없으면   =>   스택에서 최상단 노드를 뺍니다.

초기 상태

- 스택과 그래프 준비

 

1. 

DFS는 맨 처음에 시작 노드(Start Node)를 스택에 삽입하면서 시작한다. 또한 그와 동시에 시작 노드를 
방문했다고 알리는 '방문 처리' 를 해주도록 한다. ( 방문 처리 = 빨간색 )

 

 

위의 1,2번을 반복 수행한다.

 

2.

스택에 있던 최상단 노드가 1번 노드이므로 1번과 인접한 노드 중에서 방문하지 않은 2번 노드를 스택에 넣는다.

 

3.

최상단 노드가 2번 노드이므로 2번과 인접한 노드 중에서 방문하지 않은 노드인 3번 노드를 스택에 넣는다.

 

4.

최상단 노드가 3번 노드이므로 3번의 인접 노드 중 방문하지 않은 노드인 6번 노드를 스택에 넣는다.

 

5.

이어서 6번 노드가 최상단 노드이므로 6번의 인접 노드 중 방문하지 않은 7번 노드를 스택에 넣는다.

 

6.

7번 노드, 6번 노드, 3번 노드는 스택에서 빠져나온다. => 인접 노드를 전부 방문했기 때문이다.

이후에 스택에서 최상위 노드가 2번이므로 2번의 인접 노드 중 방문하지 않은 4번 노드를 스택에 넣는다.

 

7.

4번 노드의 인접 노드 중 방문하지 않은 5번 노드가 스택에 들어가고, 이후에 스택에서 하나씩 다 노드들이
빠져나오게 된다. 

 

최종 상태

따라서 방문 경로는 1 - 2 - 3 - 6 - 7 - 4 - 5 이다.

 

DFS 구현 코드

#include<iostream>
#include<vector>

using namespace std;

int number = 7;
int c[7];
vector<int> a[8];

void dfs(int x){
  if(c[x]) return; // 현재 그 노드가 방문한 노드라면 바로 함수 종료
  c[x] = true;
  cout << x << ' ';
  for(int i = 0; i < a[x].size(); i++){
    int y = a[x][i];
    dfs(y);
  }
}

int main(){
  //1과 2를 연결
  a[1].push_back(2);
  a[2].push_back(1);
  
  //1과 3을 연결
  a[1].push_back(3);
  a[3].push_back(1);

  //2와 3을 연결
  a[2].push_back(3);
  a[3].push_back(2);

  //2와 4를 연결
  a[2].push_back(4);
  a[4].push_back(2);
  
  //2와 5를 연결
  a[2].push_back(5);
  a[5].push_back(2);

  //3과 6을 연결
  a[3].push_back(6);
  a[6].push_back(3);

  //3과 7을 연결
  a[3].push_back(7);
  a[7].push_back(3);

  //4와 5를 연결
  a[4].push_back(5);
  a[5].push_back(4);

  //6과 7을 연결
  a[6].push_back(7);
  a[7].push_back(6);

  dfs(1);
}

기본적으로 재귀 호출 자체가 컴퓨터의 내부적인 구조인 스택 구조에 차곡차곡 쌓이는 형태이기 때문에
간단히 재귀함수로 구현을 하는 것 만으로도 사실 스택에 담고 빼는 것과 같은 효과가 나온다. 그렇기 때문에

스택을 따로 쓰지 않고 재귀만 구현해서 DFS를 구현하는게 알고리즘 대회에서 자주 쓰인다.