너비 우선 탐색 BFS 큐 활용 최단 거리 탐색
지형 정보가 담긴 지도에서 최단 경로를 찾거나, 소셜 네트워크 서비스에서 '아는 사람'의 단계를 계산할 때 필수적으로 요구되는 기술이 있습니다. 바로 너비 우선 탐색(Breadth-First Search, BFS)입니다. BFS는 시작 지점에서 가까운 곳부터 차례대로 탐색 범위를 넓혀가는 방식을 통해 데이터 간의 거리 관계를 명확히 규명합니다. 본 포스팅에서는 BFS의 수학적 정당성과 큐(Queue)를 활용한 구현 메커니즘을 상세히 다루어 보겠습니다[cite: 5, 238].
1. 너비 우선 탐색(BFS)의 정의와 계층적 탐색 원리
너비 우선 탐색은 시작 노드로부터 인접한 노드를 먼저 방문하고, 멀리 떨어져 있는 노드는 나중에 방문하는 방식입니다. 마치 호수에 돌을 던졌을 때 물결이 동심원을 그리며 퍼져나가는 모습과 유사합니다. 이러한 탐색 방식의 가장 큰 특징은 '레벨(Level) 단위 탐색'입니다. 출발점에서 거리가 1인 노드들을 모두 확인한 뒤에야 거리가 2인 노드들로 넘어가는 논리적 순차성을 가집니다[cite: 242].
1-1. BFS의 핵심 엔진: 큐(Queue) 자료구조
BFS의 계층적 탐색을 가능하게 하는 것은 선입선출(First-In-First-Out, FIFO) 원리의 큐 자료구조입니다. 먼저 발견된 노드가 먼저 탐색 대상이 됨으로써 탐색의 공정성과 거리순 방문을 보장합니다. 노드를 발견하면 큐의 뒤(Rear)에 넣고, 탐색을 시작할 때는 큐의 앞(Front)에서 노드를 꺼내 인접 노드들을 조사하는 과정을 반복합니다.
2. 최단 경로 보장과 BFS의 알고리즘 로직
BFS가 알고리즘 코딩 테스트와 실무에서 각광받는 이유는 가중치가 없는 그래프에서 '최단 경로'를 항상 보장하기 때문입니다. 시작점에서 특정 목표점까지 도달했을 때, 처음으로 방문하게 되는 시점의 경로가 반드시 최소 이동 횟수를 가진다는 수학적 증명이 가능합니다.
2-1. 단계별 동작 프로세스
- 시작 노드를 방문 처리하고 큐에 삽입합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- 큐에서 노드를 하나 꺼냅니다.
- 해당 노드와 연결된 인접 노드 중 아직 방문하지 않은 노드들을 모두 큐에 넣고 방문 처리합니다.
이 과정에서 각 노드까지 도달하는 데 걸린 거리를 별도의 배열에 기록하면, 출발지로부터의 모든 거리 정보를 $O(V + E)$의 시간 복잡도 내에 완벽하게 산출할 수 있습니다[cite: 242, 247].
3. BFS 활용의 실제와 주의사항
BFS는 최단 거리 탐색뿐만 아니라 네트워크 보안의 전파 모델링, 가비지 컬렉션(GC)의 도달 가능성 판별 등 다양한 전산 시스템 분야에서 활용됩니다. 다만, 탐색 과정에서 인접한 모든 노드를 메모리에 보관해야 하므로 그래프의 너비가 넓을수록 메모리 점유율이 높아질 수 있다는 점을 유의해야 합니다. 이는 공간 복잡도가 노드의 수 $V$에 정비례하는 $O(V)$의 특성을 가지기 때문입니다.
1. 탐색 철학: 가까운 이웃부터 먼저 살피는 '너비 중심'의 계층적 탐색 기법입니다.
2. 구현 도구: FIFO 방식의 큐 자료구조를 사용하여 탐색 순서를 엄격하게 관리합니다.
3. 활용 가치: 가중치 없는 그래프에서 최단 경로를 찾는 데 독보적인 효율성을 자랑합니다.