그래프 자료구조에서 특정 노드를 찾거나 전체 구조를 파악하기 위한 탐색 알고리즘은 코딩 테스트와 실무 알고리즘의 근간을 이룹니다. 그중에서도 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 각기 다른 철학을 가진 탐색 기법입니다. 어떤 상황에서 어떤 알고리즘을 선택하느냐에 따라 프로그램의 효율성과 정답 여부가 갈리기도 합니다. 본 포스팅에서는 두 알고리즘의 메커니즘을 상세히 비교하고, 실전 문제 해결을 위한 최적의 선택 기준을 제시하겠습니다.
1. 너비 우선 탐색(BFS, Breadth-First Search)의 이해
너비 우선 탐색은 시작 노드로부터 가까운 노드를 먼저 방문하고, 멀리 떨어져 있는 노드를 나중에 방문하는 방식입니다. 마치 호수에 돌을 던졌을 때 파동이 사방으로 퍼져나가는 것과 유사한 원리입니다. 이 방식은 주로 '최단 거리'를 구해야 하는 문제에서 독보적인 성능을 발휘합니다.
1-1. BFS의 동작 원리와 자료구조
BFS는 선입선출(FIFO) 방식의 큐(Queue) 자료구조를 핵심적으로 사용합니다. 탐색 과정은 다음과 같습니다. 먼저 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 이후 큐에서 노드를 꺼내 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 큐에 삽입하며 방문 처리를 반복합니다. 이러한 계층적인 탐색 특성 덕분에 처음으로 목적지에 도달했을 때의 경로가 반드시 최단 경로임을 보장할 수 있습니다.
1-2. 시간 및 공간 복잡도 분석
노드의 개수를 $V$, 간선의 개수를 $E$라고 할 때, BFS의 시간 복잡도는 $O(V + E)$입니다. 모든 노드와 간선을 한 번씩 확인하기 때문입니다. 공간 복잡도 측면에서는 인접한 노드들을 큐에 보관해야 하므로 노드의 개수에 비례하는 메모리가 필요합니다. 특히 그래프의 너비가 넓을수록 큐의 크기가 커질 수 있음에 유의해야 합니다.
2. 깊이 우선 탐색(DFS, Depth-First Search)의 이해
깊이 우선 탐색은 이름 그대로 그래프의 한 방향을 선택해 끝까지 파고든 후, 더 이상 갈 곳이 없으면 이전 갈림길로 돌아와 다른 방향을 탐색하는 방식입니다. 미로 찾기에서 한 길을 끝까지 가보는 전략과 흡사합니다. DFS는 주로 '모든 경우의 수'를 탐색하거나 그래프의 사이클 존재 여부를 확인할 때 유용합니다.
2-1. DFS의 구현 방식: 재귀와 스택
DFS는 스택(Stack) 자료구조를 사용하거나, 시스템 스택을 이용하는 재귀 함수(Recursion) 형태로 가장 많이 구현됩니다. 한 노드에 방문하면 방문 처리를 하고, 인접한 노드 중 방문하지 않은 노드가 있다면 즉시 그 노드로 들어가 탐색을 이어갑니다. 만약 주변에 더 방문할 곳이 없다면 백트래킹(Backtracking)을 통해 이전 상태로 돌아가 다른 경로를 찾습니다.
2-2. DFS의 특징과 주의점
DFS 역시 시간 복잡도는 $O(V + E)$로 효율적입니다. 하지만 BFS와 달리 발견한 경로가 최단 경로라는 보장이 없습니다. 또한, 그래프의 깊이가 매우 깊을 경우 재귀 호출의 한계로 인해 'Stack Overflow' 에러가 발생할 수 있습니다. 따라서 파이썬과 같은 언어에서는 재귀 제한을 별도로 설정해 주는 작업이 필요할 수 있습니다.
3. BFS와 DFS, 언제 무엇을 써야 할까?
두 알고리즘의 선택 기준은 문제의 요구사항에 따라 명확히 갈립니다. 이를 판단하는 것은 고수의 영역이며, 다음의 가이드라인을 참고하면 좋습니다.
상황별 최적 알고리즘 선택 기준
- 최단 거리(최소 비용)를 구할 때: 망설임 없이 BFS를 선택해야 합니다. DFS는 처음 찾은 경로가 최단 경로가 아닐 수 있어 모든 경로를 다 뒤져봐야 하지만, BFS는 레벨 단위 탐색이므로 가장 먼저 도달하는 경로가 정답입니다.
- 경로의 특징을 저장해야 할 때: 예를 들어 이동하는 경로에 특정 제약이 있거나 경로 자체를 기록해야 한다면 DFS가 유리합니다. 각 노드에 방문하며 상태를 전이하기 용이하기 때문입니다.
- 그래프의 규모가 크고 답이 얕은 곳에 있을 때: BFS가 빠를 가능성이 높습니다. 반면 답이 아주 깊은 곳에 있거나 전체를 다 훑어야 한다면 DFS가 메모리 측면에서 효율적일 수 있습니다.
1. BFS: 큐를 사용하며 최단 경로 탐색에 최적화되어 있습니다.
2. DFS: 재귀나 스택을 사용하며 모든 조합 및 사이클 판별에 유용합니다.
3. 선택 요령: '최단' 키워드가 있다면 BFS, '모든 경로'나 '특징'이 중요하다면 DFS를 우선 고려하십시오.