깊이 우선 탐색(DFS)란 ?

 

 

DFS(Depth First Search)란?

DFS란 깊이 우선 탐색으로 불리며 그래프 탐색의 한 종류이다.

루트 노드나 지정된 노드에서 시작하여 그 노드의 최대 깊이까지 탐색한 다음

더 이상 탐색 불가능하면 부모 노드로 돌아와 다른 노드로 탐색을 진행한다.

 

알고리즘 진행 모습은 이렇다.

깊이 우선 탐색 - 위키백과

이처럼 최고 깊이까지 탐색한 다음 더 이상 진행할 곳이 없으면

부모 노드로 돌아와 노드로 탐색을 진행한다.

 

순서의 2, 5, 9 노드로 순서로 진행하는 것은 조건을 어떻게 주느냐에 따라 다르다.

예를 들어 노드에 주어진 값이 가장 작은 것부터 탐색하거나

큰 값부터 탐색하는지 주어진 조건에 따라 탐색 순서는 바뀔 수 있다.

 

DFS 알고리즘 문제는 스택자료구조나 재귀 함수를 사용한다.

이때 가장 중요한 점은 방문한 노드를 방문처리하는 것이다.

방문처리하지 않으면 같은 곳을 계속 방문할 가능성이 있다.