[정보처리기사] 깊이 우선 탐색 ( DFS, Depth - First Search )

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

- 트리나 그래프를 탐색하는 기법 중 하나

- 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘

- 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만, 항상 완전탐색으로 사용되지는 않는다.

- 주로 반복문을 활용하거나, 재귀문을 통하여 구현된다.

---

■ 탐색 과정 

DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 것이다. 탐색하는 과정은 다음과 같다.

 

1. 현재 노드를 방문한 것으로 표시한다.
2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.
4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

** 아래 블로그 내용 참고

---

■ 장단점

장점	단점
현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.	순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.	두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.
DFS를 사용하여 그래프에서 순환을 감지할 수 있다.

- DFS는 특정 시나리오에서 매우 유용할 수 있지만 항상 최선의 선택은 아니다.
- 해결하려는 특정 문제에 따라 BFS( Breadth - first Search ) 와 같은 다른 알고리즘이 더 적합할 수 있다.

 

 

---

참고 및 출처 :  

https://olrlobt.tistory.com/35

[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란?