깊이 우선 탐색 (DFS)
- Depth First Search
- 깊이 우선 탐색
- 스택이 사용됨
- 재귀적인 구현이 사용될 때가 많다.
- 선수 자료 구조로 그래프를 공부해야 한다.
DFS를 사용할 때는 재귀호출(recursion)을 쓰는 게 효율적이고 효과적이다.
시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐새갛고 넘어가는 방법.
✋ 구현 시 주의 할 점은 반드시 방문한 노드에 대한 표시를 해야 한다는 것.
장점
- 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있는 경우 해를 빨리 구할 수 있다.
- 구현이 너비 우선 탐색(BFS) 보다 간단하다.
단점
- 단순 검색 속도는 너비 우선 탐색보다 느리다.
- 해가 없는 경우에 빠질 가능성이 있다.
(사전에 임의의 깊이를 지정한 후 탐색하고, 목표 노드를 발견하지 못할 경우 다음 경로를 탐색하도록 해야한다.) - 깊이 우선 탐색은 해를 구하면 탐색이 종료되므로, 구한 해가 최단 경로가 된다는 보장이 없다.
(목표에 이르는 경로가 다수인 경우, 구한 해가 최적이 아닐 수 있다.)
DFS를 활용한 좋은 문제가 있기에 관련 문제들을 연습해보면 좋을 것 같다.
developer