DFS

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

하나의 정점으로부터 시작해서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다.

기본적으로 스택구현

장점

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

단점

1. 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
   
2. 얻어진 해가 최단 경로가 된다는 보장이 없다.
   이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
   
3. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
4. 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다