깊이 우선 탐색(depth-first search, DFS)

맹목적 탐색방법의 하나로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.

스택 자료구조 혹은 재귀 함수를 이용한다.

DFS 시각화

<동작과정>

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 한다.

   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더이상 2번의 과정을 수행할 수 없을 떄까지 반복

 

<설명 예시>

 

 

깊이 제한과 백트래킹

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.
여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

 

 

장점과 단점

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.