DFS vs BFS: 미로 찾기로 비유하는 깊이 우선 vs 너비 우선 탐색

복잡한 2차원 미로에 갇혔다고 상상해 보십시오. 출구를 찾기 위해 당신이 취할 수 있는 전략은 크게 두 가지입니다. 첫 번째는 "한 방향으로 갈 수 있을 때까지 끝까지 파고들다가, 막히면 방금 지나온 갈림길로 되돌아가서 다른 길을 찾는" 방식입니다. 두 번째는 "현재 위치에서 한 발자국 갈 수 있는 모든 방향을 동시에 탐색하며, 물결이 퍼져나가듯 점진적으로 영역을 넓히는" 방식입니다. 이 두 가지 직관적인 탐색법이 바로 그래프 이론을 지배하는 양대 산맥, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)입니다. 완전히 다른 철학을 가진 두 탐색 기법의 완벽한 차이를 해부해 봅니다.

1. DFS (Depth-First Search): 끝장을 보는 직진 본능

DFS는 이름 그대로 '깊이(Depth)'를 최우선으로 삼습니다. 한 노드를 방문하면 그 노드에 연결된 자식 노드 중 하나를 골라 바닥에 도달할 때까지 무자비하게 파고듭니다.

• 핵심 무기 (재귀와 스택): 가던 길이 막혔을 때(더 이상 방문할 노드가 없을 때), 방금 전의 갈림길로 되돌아가는 백트래킹(Backtracking)이 필수적입니다. 이를 구현하기 위해 함수가 자기 자신을 부르는 '재귀(Recursion)'나, 지나온 길을 차곡차곡 쌓아두는 '스택(Stack)' 자료구조를 사용합니다.
• 장점과 단점: 메모리를 적게 차지하며, 운이 좋으면 출구를 엄청나게 빨리 찾을 수 있습니다. 하지만 찾은 경로가 '최단 경로'라는 보장이 없으며, 무한히 깊은 미궁에 빠지면 영원히 헤어 나오지 못할 위험이 있습니다.

2. BFS (Breadth-First Search): 공평하게 퍼져나가는 물결

반면 BFS는 현재 노드에서 가장 가까운 이웃 노드들을 '전부 다' 방문한 뒤에야 그다음 깊이의 노드들로 넘어갑니다. 잔잔한 호수에 돌을 던졌을 때 동심원이 퍼져나가는 모습을 상상하면 정확합니다.

• 핵심 무기 (큐): 공평한 탐색을 위해 '먼저 발견된 노드를 먼저 방문'해야 합니다. 따라서 먼저 들어온 데이터가 먼저 나가는 '큐(Queue)' 자료구조가 필수적으로 사용됩니다.
• 장점과 단점: 목표물을 발견하는 순간, 그 경로가 무조건 최단 경로(Shortest Path)임이 수학적으로 보장됩니다. 길 찾기 문제의 절대적인 정답입니다. 하지만 뻗어나가는 모든 경로를 큐에 저장해야 하므로, 메모리 소모가 DFS에 비해 극심하다는 치명적인 단점이 있습니다.

[핵심 요약]
1. DFS(깊이 우선 탐색)는 한 우물만 끝까지 파는 탐색법으로, 스택(Stack)이나 재귀 함수로 구현하며 경로의 특징(예: 제약 조건)을 기억해야 할 때 유리합니다.
2. BFS(너비 우선 탐색)는 가까운 곳부터 넓게 퍼져나가는 탐색법으로, 큐(Queue)로 구현하며 최단 거리를 보장하는 길 찾기 문제에 무조건적으로 사용됩니다.
3. 두 알고리즘 모두 모든 노드를 한 번씩 방문하므로 시간 복잡도는 $O(V+E)$ (정점 수 + 간선 수)로 동일합니다.