BFS 알고리즘(Breadth-First Search)

개요

BFS(Breadth-First Search)는 그래프나 트리의 탐색 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 탐색해 나가는 너비 우선 방식이다. 큐(Queue)를 기반으로 하며, 최단 거리 탐색과 레벨 기반 처리가 가능해 다양한 문제 해결에 널리 사용된다. 본 글에서는 BFS의 개념, 동작 원리, 시간 복잡도, 구현 방법, 활용 사례 등을 체계적으로 정리한다.

---

1. 개념 및 정의

BFS는 탐색 시작 노드에서 인접한 노드들을 먼저 방문한 뒤, 그다음 레벨의 노드들을 방문하는 방식으로 그래프를 탐색하는 알고리즘이다. FIFO 구조의 큐를 사용하며, 방문 순서가 레벨 순으로 진행된다. 무가중치 그래프에서 최단 경로를 찾는 데 가장 적합한 알고리즘이다.

---

2. BFS 알고리즘 동작 방식

단계	설명
1단계	시작 노드를 큐에 삽입하고 방문 표시
2단계	큐에서 노드를 꺼내 인접한 노드 탐색
3단계	방문하지 않은 인접 노드를 큐에 삽입하고 방문 처리
4단계	큐가 빌 때까지 반복

이 과정을 통해 그래프는 레벨 순서대로 탐색된다.

---

3. BFS 구현 (Python 예시)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS는 deque를 이용한 큐와 set을 이용한 방문 처리를 통해 구현된다.

---

4. 시간 및 공간 복잡도

요소	복잡도
시간 복잡도	O(V + E) (V: 정점 수, E: 간선 수)
공간 복잡도	O(V) (큐와 방문 리스트 사용)

그래프가 희소한 경우에도 효율적으로 동작한다.

---

5. BFS vs DFS 비교

항목	BFS	DFS
탐색 방식	너비 우선	깊이 우선
자료구조	큐	스택(또는 재귀)
최단 경로 보장	O	X
메모리 사용	높을 수 있음	상대적으로 적음
사용 예시	최단 거리, 레벨 탐색	백트래킹, 조합 탐색

BFS는 구조적 탐색에, DFS는 깊이 중심 문제에 적합하다.

---

6. 주요 활용 사례

분야	활용 예시
게임 개발	맵의 최단 경로 탐색, NPC 경로 설정
네트워크 분석	소셜 네트워크 그래프의 연결성 탐색
인공지능	퍼즐, 미로 탈출 문제에서 최단 거리 계산
웹 크롤링	페이지 간 링크 레벨별 탐색
알고리즘 문제풀이	최소 이동 횟수, BFS 기반 탐색 문제 (ex. 토마토, 미로, 물 퍼오기 등)

BFS는 단순하면서도 강력한 탐색 방식으로 실전에서 널리 쓰인다.

---

7. 결론

BFS는 너비 우선 탐색 방식으로 그래프와 트리의 구조적 탐색, 최단 거리 문제 해결, 레벨 순서 탐색 등에 매우 효과적인 알고리즘이다. 큐를 활용한 구조와 O(V+E)의 시간 복잡도를 바탕으로 다양한 문제에 빠르고 안정적으로 적용 가능하다. DFS와 함께 알고리즘 문제 해결의 양대 산맥으로 실전에서 반드시 익혀야 할 기본 탐색 기법이다.