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

깊이 우선 탐색(DFS, Depth-First Search)

트리나 그래프의 하나의 정점의 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 깊게 전부 먼저 탐색해 나가는 방법입니다. 마치 미로에서 갈수있는 끝까지 갔다가 가장 가까운 갈림길에서 다시 탐색을 시작하는 방법과 유사합니다.

 

왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊이를 먼저 넓게(wide) 탐색하는 것을 볼 수 있습니다.

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

• DFS는 일반적으로 스택이나 재귀호출을 통해 구현합니다. (재귀호출을 통한 메서드 스택)
• 리프노드를 한 번에 잘라내기 용이하여 백트래킹 알고리즘에 자주 사용됩니다.
• 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 합니다

깊이 우선 탐색(DFS)의 장단점

장점

• 목표가 깊은곳에 위치할 경우 동일 레벨을 모두 먼저 탐색하는 너비우선탐색(BFS)보다 속도가 빠릅니다.
• 지나온 경로만 확인하면 되므로 BFS보다는 적은 공간이 필요합니다.

단점

• 찾아낸 목표가 최단거리의 최적해가 아닐 수 있습니다.
• 일반적으로 BFS보다 속도가 느립니다.
• 해가 없는 경로로 깊이 먼저 탐색 할 경우 최악의 탐색 성능이 나올 수 있습니다.
• 스택으로 구현시 구현시 스택오버플로우에 유의해야합니다.

DFS 문제 예제 - LeetCode

LeetCode에서 DFS를 이해하기 좋은 예시 문제 풀이들입니다.

[LeetCode] 733. Flood Fill - 문제풀이

[LeetCode] 695. Max Area of Island - 문제풀이