[자료구조] Depth First Search, DFS (깊이 우선 탐색)

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

: root node 에서 시작해서 다음 Branch 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사. 

즉, 넓게(wide) 탐색하기 전에 깊게 (deep) 탐색하는 것이다.

모든 노드를 방문하고자 하는 경우에 DFS를 사용한다. 

DFS(Depth First Search)가 BFS(Breadth First Search) 보다 더 simple 하다.

단순 검색 속도 자체는 DFS 가 BFS 에 비해 느리다. 

 

#깊이 우선 탐색(DFS)의 특징

자기 자신을 호출하는 순환 알고리즘 형태를 가지고있음.

Pre-Order-Traversals 를 포함한 다른 형태의 Tree Traversals 는 모두 DFS 의 한 종류이다. 

이 알고리즘을 구현할 때, 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사한다는 것.

(이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다. )