들어가며
알고리즘 공부 중에 새롭게 알게 된 결정 깊이 우선 탐색에 대해 작성하였습니다.
깊이 우선 탐색(Depth-First Search)
트리나 그래프를 탐색하는 기법 중 하나로, 시작노드부터 자식 노드를 순서대로 탐색하는 방식입니다. 탐색 순서 결정 시 깊이를 우선시하며, 루트노드의 분기에서 다음 분기를 넘어갈 때 한쪽의 문기를 완벽하게(즉, 가장 깊은 곳까지) 탐색 후 넘어가는 방식입니다.
DFS의 구현 및 특징
DFS는 주로 다음 방식들 중 하나를 사용하여 구현합니다.
- 반복 DFS : 반복문 + 명시적 스택(Stack 자료구조 활용)
- 재귀 DFS : 재귀호출 (스택 메모리 사용)
그리고 다음의 순서로 노드를 탐색합니다.
- 현재 노드를 방문한 노드로 처리한다.
- 현재 노드의 자식 노드 중 방문하지 않은 노드가 있는지 확인한다.
- 방문하지 않은 노드가 있다면 해당 노드로 이동(방문)하고, 1~2 과정을 반복한다.
- 더 이상 방문할 인접 노드가 없다면 스택에서 꺼내며 이전 노드로 되돌아간다 (backtracking).
- 이렇게 2~5의 과정을 반복하여 모든 노드를 순회한다.
DFS를 구현하는 두가지 방법 모두 위와 같은 순서로 처리됩니다. 다만 Stack을 명시적으로 사용하느냐, 스택 메모리를 활용하느냐의 차이가 있습니다.
반복 DFS의 경우 다음의 특징이 있습니다.
- Stack 자료구조를 사용하므로 Heap 메모리를 사용합니다.
- Heap 메모리를 사용하기 때문에 그래프의 깊이가 깊어도 stack overflow가 발생하지 않음므로 안전합니다.
- 다만, 재귀 DFS에 비해 백트래킹 상태를 자동으로 기억하지 않으므로, 필요한 경우 상태(예: 다음 이웃 인덱스)를 직접 저장·관리해야 합니다. 때문에 재귀 DFS에 비해 코드 가독성이 떨어질 수 있습니다.
재귀 DFS의 경우 다음의 특징이 있습니다.
- 재귀함수이기 때문에 Stack 메모리를 활용합니다.
- 재귀 스택에 탐색 깊이만큼 스택 메모리에 쌓이고, 시스템에 의해 pop 처리 되므로 별도의 Stack 구현 및 백트랙킹 상태를 기록하지 않아도 된다.
- 다만, 스택 메모리를 활용하기 때문에 깊이가 길어지면 stack overflow가 발생할 수 있다.
너비 우선 탐색 (Breadth-First Search)
마찬가지로 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드부터 가까운 순서로 진행되며 점차 깊이 내려가는 방식입니다. 같은 깊이에 있는 노드들은 서로 인접하지 않아도 동일한 레이어로 간주합니다.
BFS의 구현 및 특징
BFS는 구현시 다음 순서로 진행됩니다.
- 시작 노드를 Queue에 넣는다.
- Queue에서 노드를 꺼내 방문 처리한다.
- 해당 노드와 인접한 모든 노드 중 방문하지 않은 노드를 Queue에 넣는다.
- 2~3의 과정을 반복한다.
BFS는 구현시 다음의 특징을 가지고 있습니다.
- DFS와 마찬가지로 방문한 노드를 반드시 체크해야 한다.
- DFS와 달리 재귀 호출을 사용하지 않는다.
- DFS와 다르게 Stack이 아닌 Queue를 이용하여 구현한다.
DFS vs BFS (선택 기준)
일반적으로 DFS나 BFS는 서로 바꿔서 사용해도 해결되는 경우가 많습니다. 다만 사용하면 훨씬 빠르거나 보다 효율적인 상황들이 존재합니다.
DFS를 고려해야하는 경우는 다음과 같습니다.
- 노드 전체를 순회해야하는 경우. 즉, 모든 노드를 조사해야하는 경우
- 모든 경우를 다 찾아야 하는 경우. 순열, 조합 구현 등에서 활용
- 미로 찾기 등의 경로를 추적해야하는 경우 유용
- 그래프의 사이클 유무 확인, 연결 요소 확인 등의 구조적 특징 파악 시 유용
- 조사 대상의 깊이가 깊은 경우
BFS를 고려해얗하는 경우는 다음과 같습니다.
- 특정 노드 중심으로 조사해야하는 경우
- 조사 대상의 넓이가 넓은 경우
- 주로 최단 경로 조사에서 사용
마치며
개인적인 느낌으로 미로 탐색하는 방법 중 오른손 법칙이랑 비슷하다는 생각이 듭니다. 한쪽으로만 쭉 향하다가 막히면 되돌아가고 이런식으로 진행한다는 점이 유사한 것 같습니다. 물론 DFS의 경우 전체를 탐색하게 된다는 등의 차이는 있지만 추후 유사한 문제에서 활용할 수 있지 않을까 생각이 듭니다. 읽어주셔서 감사합니다.
참고자료
[깊이 우선 탐색]
Depth First Search (DFS) with Explanation and Code
[알고리즘] 깊이 우선 탐색(DFS)이란
[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란?
[DFS의 구현 및 특징]
반복과 재귀 : DFS 문제를 재귀로 구현하면 편리한 이유
파이썬 dfs 재귀 및 반복문 시간복잡도 관련 질문 드립니다.
DFS Recursive vs DFS Iterative [duplicate]
[너비 우선 탐색]
Breadth First Search
[알고리즘] 너비 우선 탐색(BFS)이란
[BFS의 구현 및 특징]
[DFS vs BFS (선택 기준)]
What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
[알고리즘] 언제 BFS를, DFS를 써야할까?
DFS/BFS 개념 및 문제 접근 방법
PS를 하며 느끼는 DFS와 BFS 선택의 기준
자바로 알아보는 DFS와 BFS
