깊이 우선 탐색(DFS) 이란?

DFS는 Depth-Fist-Search, 깊이 우선 탐색이라고 부르며,

그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

힌쪽 갈림길을 택하면서 갈 수 있는 최대한 깊이 들어가면서 그래프 or 트리를 탐색한다.

더 이상 갈 곳이 없을 때까지 길을 따라간다. 막다른 길이 나오면, 마지막으로 갈림길이 나왔던 지점으로 돌아간다.

이 때, 마지막 지점으로 돌아가는 것을 스택의 LIFO(후입선출)을 활용해 돌아간다.

Untitled

Untitled

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다.

위의 오른쪽 그림처럼 0에서 1로, 1에서 3으로 갔을 때 더 이상 갈 곳이 없으면 백 트랙킹(Back Tracking)을 해서

다시 1로 가게 된다. 이후에 방문하지 않은 4를 방문하게 되는 형태다.

DFS는 대게 스택을 사용하고 모든 노드를 방문하고자 할 때 사용한다.

BFS보다 더 간단하게 구현되지만 검색 속도는 BFS에 비해 느리다.

<aside> 📖

Info. 굳이 DFS로 풀어야 하는 문제는 존재하지 않는다. BFS로 해결할 수 있다.

</aside>

깊이 우선 탐색 과정