[알고리즘] DFS(Depth-First Search) 깊이 우선 탐색

DFS란?

Depth-First Search의 줄임말로 깊이 우선 탐색이라고 합니다.

그래프 탐색 알고리즘 중 하나로 한 루트로 최대한 깊숙이 들어가서 확인한 뒤

가장 가까운 곳으로 돌아가 다른 루트로 탐색하는 방식입니다.

미로 찾기에서 한 방향으로 끝까지 갔다가 막히면 그곳에서 가장 가까운 갈림길부터 다시 찾는 것입니다.

모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다.

 

특징

• 일반적으로 재귀호출을 사용하여 구현한다.
• 스택이 사용된다.
• 어떤 노드를 방문했었는지 여부를 검사해야 한다
  • 그렇지 않을 경우 무한루프에 빠질 수 있다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

 

출처: 하나몬

 

0 - 1 - 3 - 4 - 2 - 5 - 6 순으로 탐색하게 됩니다.

 

코드로 구현해보기

 

방문한 순서가 잘 나오는 것을 볼수 있습니다.