두 개는 거의 세트로 이야기가 되기 때문에 같이 집필했다.

DFS

Depth Firsth Search 깊이 우선 탐색

트리나 그래프 자료구조에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다.

일반적으로 재귀호출을 사용하여 구현하지만 단순한 스택 배열로 구현할 수도 있다.

단순 검색 속도 자체는 BFS에 비해서 느리다. 하지만 검색이 아닌 순회를 할 경우는 많이 쓰인다.

자동 미로 생성에 많이 사용되는 알고리즘이다.

장점

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

단점

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