Dev Chongmin

DFS(Depth First Search)란?

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

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

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

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

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

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

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

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

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

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

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

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

최근 DFS와 BFS 자료구조 문제를 풀려고 시도하는데 구현에 어려움이 있어서 

개념을 정리 후에 다시 풀어보려고 작성한 글입니다.