DFS는 Depth-Fist-Search, 깊이 우선 탐색이라고 부르며,
그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
힌쪽 갈림길을 택하면서 갈 수 있는 최대한 깊이 들어가면서 그래프 or 트리를 탐색한다.
더 이상 갈 곳이 없을 때까지 길을 따라간다. 막다른 길이 나오면, 마지막으로 갈림길이 나왔던 지점으로 돌아간다.
이 때, 마지막 지점으로 돌아가는 것을 스택의 LIFO(후입선출)을 활용해 돌아간다.


DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다.
위의 오른쪽 그림처럼 0에서 1로, 1에서 3으로 갔을 때 더 이상 갈 곳이 없으면 백 트랙킹(Back Tracking)을 해서
다시 1로 가게 된다. 이후에 방문하지 않은 4를 방문하게 되는 형태다.
DFS는 대게 스택을 사용하고 모든 노드를 방문하고자 할 때 사용한다.
BFS보다 더 간단하게 구현되지만 검색 속도는 BFS에 비해 느리다.
<aside> 📖
Info. 굳이 DFS로 풀어야 하는 문제는 존재하지 않는다. BFS로 해결할 수 있다.
</aside>