BFS(Breadth First Search)

BFS(Breadth First Search)는 그래프를 탐색하는 방법 중 하나로, 가까운 노드부터 차례대로 넓게 탐색해 나가는 방식이다. DFS가 한 방향으로 깊게 파고드는 탐색이었다면, BFS는 현재 위치에서 같은 거리(같은 단계)에 있는 노드들을 먼저 모두 방문한 뒤 다음 단계로 넘어간다. 그래서 BFS는 “깊이”보다는 “거리”에 더 초점이 맞춰진 탐색 방법이라고 볼 수 있다.

BFS의 탐색 흐름은 비교적 직관적이다. 시작 노드에서 출발해, 그 노드와 직접 연결된 모든 노드를 먼저 방문한다. 그 다음에는 방금 방문한 노드들과 연결된 노드들을 다시 한 번 전부 확인한다. 이런 식으로 한 단계씩 범위를 넓혀가며 탐색이 진행된다. 마치 물에 돌을 던졌을 때 파동이 동심원 형태로 퍼져 나가는 모습과 비슷하다.

이러한 탐색 순서를 유지하기 위해 BFS는 큐(Queue) 자료구조를 사용한다. 먼저 발견한 노드를 먼저 처리해야 하기 때문이다. 시작 노드를 큐에 넣고, 하나를 꺼내서 그와 인접한 노드들을 다시 큐에 넣는 과정을 반복하면, 자연스럽게 “가까운 노드부터” 탐색하는 구조가 만들어진다. 이 과정에서도 DFS와 마찬가지로, 이미 방문한 노드를 다시 방문하지 않도록 방문 여부를 반드시 관리해야 한다.

BFS의 시간 복잡도는 DFS와 동일하다. 인접 리스트로 그래프를 표현했을 때, 모든 노드를 한 번씩 방문하고 모든 간선을 한 번씩 확인하므로 O(N + M)의 시간 복잡도를 가진다. 여기서 N은 노드의 개수, M은 간선의 개수다. 탐색 순서만 다를 뿐, 그래프 전체를 훑는다는 점에서는 DFS와 동일한 비용이 든다.

BFS가 특히 강점을 가지는 상황은 최단 거리와 관련된 문제다. 예를 들어 “A에서 B까지 가장 적은 단계로 도달할 수 있는가?”, “최소 몇 번의 이동으로 목적지에 도착할 수 있는가?” 같은 질문에는 BFS가 매우 적합하다. BFS는 가까운 노드부터 탐색하기 때문에, 어떤 노드를 처음 방문했을 때 그 경로가 곧 최단 경로가 된다. 이 때문에 미로 탐색, 최단 경로 문제, 레벨 단위 탐색이 필요한 문제에서 BFS가 자주 사용된다.

정리하자면, BFS는 그래프를 넓게 퍼지듯 탐색하는 알고리즘이다. 큐를 기반으로 동작하며, 시작점으로부터의 거리를 기준으로 노드를 방문한다는 점이 핵심이다. DFS가 “끝까지 파고들어 본다”는 탐색이라면, BFS는 “가까운 것부터 하나씩 확인한다”는 탐색이다. 이 차이만 명확히 이해해두면, 두 알고리즘을 언제 어떤 문제에 사용해야 할지도 자연스럽게 구분할 수 있다.