복잡한 미로에 갇혔다고 상상해 봅시다. 출구를 찾기 위해 여러분은 어떤 전략을 사용하시겠습니까? 한쪽 길을 정해서 막다른 벽이 나올 때까지 무조건 직진해 보시겠습니까, 아니면 현재 서 있는 갈림길에서 갈 수 있는 모든 방향을 한 걸음씩 확인하며 신중하게 나아가시겠습니까? 이 두 가지 전략이 바로 그래프 탐색의 양대 산맥인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 개발자 면접이나 코딩 테스트에서 이 두 알고리즘의 차이를 묻는다면, 단순히 탐색 순서뿐만 아니라 사용되는 자료구조(스택 vs 큐)와 해결할 수 있는 문제의 종류가 다르다는 점을 명확히 설명해야 합니다.
1. DFS (Depth-First Search): 깊이 우선 탐색
DFS는 이름 그대로 '깊이(Depth)'를 우선시하는 탐색 방법입니다. 한 놈만 팬다는 마인드와 비슷합니다. 루트 노드(혹은 임의의 시작점)에서 시작하여 다음 분기(Branch)로 넘어가기 전에, 해당 분기를 완벽하게 파고들어 끝을 보는 방식입니다.
1-1. 동작 원리와 특징
- 동작 방식: 갈림길이 나타나면 무조건 한쪽 방향(예: 왼쪽)을 선택해 가장 깊은 곳까지 들어갑니다. 더 이상 갈 곳이 없으면(막다른 길), 가장 가까운 갈림길로 되돌아와서(Backtracking) 다른 방향을 탐색합니다.
- 구현 자료구조: 스택(Stack)을 사용하거나 재귀 함수(Recursion)를 이용해 구현합니다. 함수 호출 자체가 스택 메모리를 사용하기 때문에 재귀가 가장 흔하게 쓰입니다.
- 장점: 현재 경로상의 노드들만 기억하면 되므로, 도달해야 할 목표가 깊은 단계에 있을 때 유용하며 BFS보다 메모리 소비가 적을 수 있습니다.
2. BFS (Breadth-First Search): 너비 우선 탐색
BFS는 '너비(Breadth)'를 우선시하는 탐색 방법입니다. 돌다리도 두들겨 보고 건너는 신중한 방식입니다. 시작 노드에서 가장 가까운 노드들부터 모두 방문하고, 그다음으로 먼 노드들을 방문하는 식으로 동심원을 그리며 퍼져 나갑니다.
2-1. 동작 원리와 특징
- 동작 방식: 시작점인 1단계 노드들을 모두 방문합니다. 그 작업이 끝나면 1단계 노드들과 연결된 2단계 노드들을 모두 큐에 넣고 방문합니다. 이렇게 층(Level)별로 탐색을 진행합니다.
- 구현 자료구조: 큐(Queue)를 사용합니다. "먼저 발견한 길을 먼저 가본다(FIFO)"는 원칙이 필수적이기 때문입니다. 재귀로는 구현이 어렵습니다.
- 장점: 출발지에서 목적지까지의 최단 경로(Shortest Path)를 보장합니다. 가까운 곳부터 찾기 때문입니다.
3. DFS vs BFS 한눈에 비교하기
이 둘은 탐색한다는 목적은 같지만, 용도가 완전히 다릅니다.
| 구분 | DFS (깊이 우선) | BFS (너비 우선) |
|---|---|---|
| 핵심 자료구조 | 스택 (Stack) / 재귀 | 큐 (Queue) |
| 탐색 스타일 | 한 우물만 판다 (직진) | 주변부터 훑는다 (확산) |
| 최단 경로 보장 | 보장 못 함 (운 좋으면 빠름) | 항상 보장함 |
| 주요 활용 | 미로 생성, 사이클 탐지 | 내비게이션, 최단 거리 |
4. 실전 문제: 언제 무엇을 써야 할까?
코딩 테스트 문제를 만났을 때 다음 기준을 적용하세요.
- BFS를 써야 할 때: "최소 이동 횟수를 구하라", "가장 빠른 길을 찾아라", "지구촌 친구 몇 단계(촌수)인지 구하라" 등 최단 거리와 관련된 모든 문제는 무조건 BFS입니다. DFS로 풀면 시간 초과가 나거나 엉뚱한 경로를 최단 경로로 착각할 수 있습니다.
- DFS를 써야 할 때: "경로가 존재하는지 확인하라", "가능한 모든 경우의 수를 다 찾아라", "퍼즐을 풀어라" 등 완전 탐색이나 경로의 특징을 저장해야 하는 경우에 적합합니다. 구현이 BFS보다 조금 더 간결한 편입니다.
[핵심 요약]
1. DFS는 스택/재귀를 사용해 깊게 파고들며, 모든 경로를 완벽히 탐색할 때 유리합니다.
2. BFS는 큐를 사용해 넓게 퍼져나가며, 출발지에서 목적지까지의 최단 경로를 찾을 때 필수적입니다.
3. 문제에서 "최소 비용"이나 "최단 거리"를 묻는다면 주저 없이 BFS를 선택해야 합니다.
1. DFS는 스택/재귀를 사용해 깊게 파고들며, 모든 경로를 완벽히 탐색할 때 유리합니다.
2. BFS는 큐를 사용해 넓게 퍼져나가며, 출발지에서 목적지까지의 최단 경로를 찾을 때 필수적입니다.
3. 문제에서 "최소 비용"이나 "최단 거리"를 묻는다면 주저 없이 BFS를 선택해야 합니다.