#15. 깊이 우선 탐색(Depth First Search, DFS)

깊이 우선 탐색(Depth First Search, DFS)

• 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식

• 자기 자신을 호출하는 순환 알고리즘의 형태

 

시간복잡도 (N : 노드, E : 간선)

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

 

깊이 제한과 백트래킹(backtracking)

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

• 여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

---

구현 방법

• 순환 호출 이용 (재귀 함수로 구현)
• 명시적인 스택 사용

 

활용

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
• 경로의 특징을 저장해두어야하는 문제
• 최단거리를 구해야 하는 문제

---

장점

• 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

• 너비 우선 탐색(BFS) 보다 구현이 간단하다.

 

단점

• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.

• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

---

References

 

ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

velog.io/@sohi_5/algorithmDFS

[자료구조와 알고리즘] DFS (깊이 우선 탐색)

devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)