BFS와 DFS는 그래프(Graph)의 모든 정점을 방문하는 대표적인 그래프 탐색 알고리즘입니다. 두 알고리즘은 탐색 방향과 사용하는 자료구조에서 핵심적인 차이를 보이며, 이러한 차이 때문에 각각 다른 상황에서 더 효율적으로 동작합니다.
BFS(Breadth First Search, 너비 우선 탐색)
BFS는 그래프를 너비 방향으로 순회하는 알고리즘입니다. 시작 정점에서 가까운 정점부터 인접한 노드들을 차례대로 방문하며, 큐(Queue)를 사용해 다음에 탐색할 정점을 기억합니다. 탐색 중 막다른 길(dead end)에 도달하면 큐에 저장된 다음 정점부터 이어서 탐색을 진행합니다.
이러한 특성 덕분에 BFS는 시작 지점에서 목표 지점까지의 최단 경로를 보장할 수 있어, 최단 거리 계산이 필요한 문제에 널리 활용됩니다.
DFS(Depth First Search, 깊이 우선 탐색)
DFS는 그래프를 깊이 방향으로 순회하는 알고리즘입니다. 하나의 경로를 따라 가능한 한 깊게 들어간 후, 더 이상 진행할 수 없으면 되돌아가(backtracking) 다른 경로를 탐색합니다. 이때 스택(Stack)을 사용해 다음에 탐색할 정점을 관리하며, 재귀 호출로 구현할 수도 있습니다.
DFS는 특정 경로를 끝까지 추적해야 하는 문제나, 그래프의 구조적 특성을 파악해야 하는 상황에서 유용하게 사용됩니다.
BFS와 DFS 주요 차이점 비교표
| 번호 | 구분 기준 | BFS | DFS |
|---|---|---|---|
| 1 | 정의 | BFS는 Breadth First Search(너비 우선 탐색)의 약자입니다. | DFS는 Depth First Search(깊이 우선 탐색)의 약자입니다. |
| 2 | 자료구조 | 큐(Queue)를 사용하여 최단 경로를 탐색합니다. | 스택(Stack)을 사용하여 경로를 탐색합니다. |
| 3 | 목표 지점의 위치 | 목표가 시작 지점(source)에 가까울 때 더 효율적입니다. | 목표가 시작 지점에서 멀리 있을 때 더 효율적입니다. |
| 4 | 결정 트리 적합성 | 모든 인접 노드를 고려하기 때문에 퍼즐 게임 등에 사용되는 결정 트리에는 적합하지 않습니다. | 결정 트리에 더 적합합니다. 하나의 결정을 내린 뒤 그 결과를 바탕으로 다음 단계를 탐색하고, 결론에 도달하면 탐색을 종료할 수 있습니다. |
| 5 | 속도 | DFS보다 상대적으로 느립니다. | BFS보다 상대적으로 빠릅니다. |
| 6 | 시간 복잡도 | O(V+E) — V는 정점(vertices), E는 간선(edges)의 수입니다. | 역시 O(V+E) — V는 정점, E는 간선의 수입니다. |
추가로 알아두면 좋은 점
공간 복잡도: BFS는 같은 깊이의 모든 노드를 큐에 저장해야 하므로 일반적으로 DFS보다 더 많은 메모리를 사용합니다. 반면 DFS는 현재 경로의 노드만 저장하므로 메모리 사용량이 상대적으로 적습니다.
대표 활용 사례: BFS는 미로 찾기의 최단 경로, 소셜 네트워크의 친구 추천, 웹 크롤링 등에 활용되고, DFS는 사이클(cycle) 검출, 위상 정렬(Topological Sort), 연결 요소(Connected Component) 탐색 등에 활용됩니다.
알고리즘 선택 기준: 최단 경로가 보장되어야 한다면 BFS를, 메모리 제약이 있거나 한 경로를 깊이 탐색해야 하는 문제라면 DFS를 선택하는 것이 일반적입니다.