넓이 우선 탐색
넓이 우선 탐색(Breadth-First Search, BFS)은 그래프(Graph)나 트리(Tree)와 같은 자료 구조에서 노드(Node)를 탐색하는 알고리즘 중 하나이다. 시작 노드로부터 거리가 1인 모든 노드를 먼저 탐색하고, 그 다음 거리가 2인 모든 노드를 탐색하는 방식으로, 가까운 노드부터 차례대로 넓게 탐색해 나간다.
개요
넓이 우선 탐색은 그래프 탐색의 가장 기본적인 방법 중 하나로, 일반적으로 큐(Queue) 자료 구조를 이용하여 구현된다. 시작 노드에서부터 연결된 인접 노드들을 먼저 방문하고, 방문한 인접 노드들과 연결된 아직 방문하지 않은 노드들을 그 다음으로 방문하는 방식이다. 이러한 탐색 순서는 시작 노드로부터의 거리가 짧은 노드들을 우선적으로 방문하게 한다.
원리 및 알고리즘
넓이 우선 탐색은 다음과 같은 단계로 진행된다.
- 탐색을 시작할 시작 노드를 선택하고, 이 노드를 방문했음을 표시한다.
- 시작 노드를 큐(Queue)에 삽입한다.
- 큐가 빌 때까지 다음 과정을 반복한다.
- 큐에서 노드를 하나 꺼낸다.
- 꺼낸 노드와 연결된 모든 인접 노드들을 확인한다.
- 인접 노드들 중에서 아직 방문하지 않은 노드가 있다면, 해당 노드를 방문했음을 표시하고 큐에 삽입한다.
이 과정을 통해 시작 노드로부터 거리가 1인 노드들이 모두 큐에 삽입되고 처리된 후, 거리가 2인 노드들이 큐에 삽입되어 처리되는 식으로 레벨별 탐색이 이루어진다.
특징
- 최단 경로 탐색: 가중치(Weight)가 없는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로(간선의 수가 가장 적은 경로)를 찾는데 유용하다. BFS는 레벨별로 탐색하기 때문에, 어떤 노드를 처음 방문했을 때의 경로는 시작 노드로부터 그 노드까지의 최단 경로임이 보장된다.
- 완전성: 유한 그래프에서 모든 도달 가능한 노드를 탐색한다.
- 시간 복잡도: 그래프의 모든 정점(V)과 간선(E)을 최대 한 번씩 방문하므로, 시간 복잡도는 O(V + E)이다.
- 공간 복잡도: 최악의 경우, 큐에 그래프의 모든 정점이 저장될 수 있으므로 공간 복잡도는 O(V)이다. 너비가 넓은 그래프일수록 많은 메모리를 요구할 수 있다.
응용 분야
넓이 우선 탐색은 다양한 분야에서 활용된다.
- 가중치 없는 그래프에서의 최단 경로 문제 해결
- 두 노드 간에 경로가 존재하는지 확인 (연결성 확인)
- 컴퓨터 네트워크에서 최단 경로 찾기
- 웹 크롤러(Web Crawler)가 웹 페이지를 탐색하는 방식 (링크를 따라가며 레벨별로 확장)
- 퍼즐이나 게임 등에서 가능한 모든 상태 공간을 탐색하여 최단 해결책을 찾는 문제
- 소셜 네트워크에서 사람들과의 연결 관계를 탐색 (몇 단계를 거쳐 연결되는가 등)
깊이 우선 탐색(DFS)과의 비교
넓이 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 그래프 탐색의 대표적인 두 방법이다.
- 탐색 순서: BFS는 시작 노드에서 가까운 노드부터 너비 방향으로 탐색하는 반면, DFS는 가능한 깊이까지 탐색한 후 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색한다.
- 사용 자료 구조: BFS는 주로 큐를 사용하는 반면, DFS는 주로 스택(재귀 호출 포함)을 사용한다.
- 활용: BFS는 최단 경로 탐색(가중치 없는 그래프)에 유리하며, DFS는 모든 노드를 방문하거나 특정 노드의 존재 여부를 확인하는 문제 등에 주로 사용되지만, 사이클 감지 등 다른 활용도 많다. 메모리 측면에서는 너비가 넓은 그래프는 BFS가, 깊이가 깊은 그래프는 DFS가 더 많은 메모리를 요구할 수 있다.