[알고리즘] 깊이 우선 탐색(DFS, Depth First Search)이란? 깊이 우선 탐색(DFS, Depth-First Search) 트리나 그래프의 하나의 정점의 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 깊게 전부 먼저 탐색해 나가는 방법입니다. 마치 미로에서 갈수있는 끝까지 갔다가 가장 가까운 갈림길에서 다시 탐색을 시작하는 방법과 유사합니다. 왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊이를 먼저 넓게(wide) 탐색하는 것을 볼 수 있습니다. 깊이 우선 탐색(DFS)의 특징 DFS는 일반적으로 스택이나 재귀호출을 통해 구현합니다. (재귀호출을 통한 메서드 스택) 리프노드를 한 번에 잘라내기 용이하여 백트래킹 알고리즘에 자주 사용됩니다. 어떤 노드를 방문했.. 알고리즘/이론 2022. 3. 7. 06:21
