그래프나 트리 구조를 탐색할 때, “가까운 곳부터 훑을 것인가(BFS)” 아니면 “한 방향을 끝까지 파고들 것인가(DFS)”라는 두 가지 상반된 전략이 존재한다.
문제의 요구사항에 따른 최적의 알고리즘 선택 기준을 분석한다.
BFS (Breadth-First Search): 최단 경로 탐색
시작 노드에서 가까운 노드부터 순차적으로 방문하는 방식이다.
큐(Queue) 자료구조를 사용하여 구현한다.
- 강점: 가중치가 없는 그래프에서 최단 경로를 보장한다.
- 복잡도:
O(V + E)(V: 노드 수, E: 간선 수)
DFS (Depth-First Search): 깊이 중심 탐색
한 방향으로 갈 수 있을 때까지 탐색하다가 막히면 되돌아와 다른 경로를 찾는 방식이다.
스택(Stack)이나 재귀 함수를 사용하여 구현한다.
- 강점: 모든 노드를 방문하거나 경로의 특징(사이클 등)을 저장해야 할 때 유리하다.
- 복잡도:
O(V + E)
전략 선택의 기준
| 항목 | BFS | DFS |
| :— | :— | :— |
| 사용 자료구조 | 큐 (Queue) | 스택 / 재귀 |
| 주요 용도 | 최단 거리, 미로 찾기 | 경로 탐색, 사이클 확인 |
| 공간 복잡도 | 너비에 비례 | 깊이에 비례 |
P.S
알고리즘 선택은 문제의 본질을 파악하는 과정이다.
“최단 거리”가 핵심이라면 BFS를, “모든 가능성 확인”이나 “복잡한 제약 조건”이 핵심이라면 DFS를 우선적으로 고려해야 하는 것 같다.
