BFS(Breadth-First Search)는 그래프 탐색에서 가장 기본적이면서도 강력한 도구 중 하나다. 그 핵심은 가까운 정점부터 탐색하는 것이다. 이 글에서는 BFS의 작동 원리, 구현 방법, 시간 복잡도, 실전 문제 적용까지 체계적으로 설명한다.
BFS란 무엇인가?
BFS는 시작 정점으로부터 거리가 가까운 정점들을 우선적으로 탐색하는 알고리즘이다. 탐색 과정에서 큐(Queue) 자료구조를 활용하여 다음 탐색할 정점을 순차적으로 관리한다. 깊게 들어가기보다는 넓게 퍼지듯이 탐색하는 방식이기 때문에 너비 우선 탐색이라는 이름이 붙었다.
BFS의 작동 원리
BFS의 기본 흐름은 다음과 같다.
- 시작 정점을 큐에 넣고 방문 표시를 한다.
- 큐에서 정점을 꺼낸다.
- 해당 정점과 인접한, 아직 방문하지 않은 정점들을 모두 큐에 추가하고 방문 표시를 한다.
- 큐가 빌 때까지 이 과정을 반복한다.
이러한 구조 덕분에 BFS는 탐색 단계별로 거리가 정확히 1씩 증가하게 된다. 따라서 최단 경로를 구해야 하는 문제에서 매우 유용하게 쓰인다.
BFS 기본 구현
BFS는 deque를 이용해 효율적으로 큐를 구현할 수 있다. 다음은 기본적인 BFS 파이썬 코드다.
from collections import deque
def bfs(graph, start):
queue = deque([start])
visited = set()
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의 시간 복잡도
BFS는 그래프의 노드 수를 N, 간선 수를 E라고 할 때 O(N + E) 의 시간 복잡도를 가진다. 모든 정점을 한 번씩 방문하고, 각 간선 역시 한 번씩만 탐색하기 때문이다.
BFS와 최단거리 탐색
가중치가 모두 1인 그래프에서 BFS는 최단 거리를 보장한다. 다음은 최단 거리를 구하는 BFS 예시다.
from collections import deque
def bfs_shortest_path(graph, start):
distance = {node: -1 for node in graph}
queue = deque([start])
distance[start] = 0
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if distance[neighbor] == -1:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
BFS를 통해 시작 정점으로부터 모든 정점까지의 최단 거리를 한 번에 구할 수 있다.
BFS의 다양한 활용
BFS는 다양한 문제 유형에서 응용된다.
- 미로 탐색: 최단 거리 구하기 (예: 백준 2178번)
- 상태 공간 탐색: 퍼즐 문제 해결 (예: 백준 13460번 구슬 탈출)
- 영역 세기: 덩어리 개수 세기 (예: 백준 2468번 안전 영역)
- 다중 BFS: 여러 출발점에서 동시에 탐색 (예: 백준 9376번 탈옥)
이처럼 BFS는 최단 경로뿐만 아니라, 다양한 그래프 기반 문제를 해결하는 핵심 기법이다.
BFS와 DFS의 비교
| 항목 | BFS | DFS |
|---|---|---|
| 탐색 방법 | 가까운 곳부터 | 깊은 곳부터 |
| 자료구조 | 큐 | 스택 (또는 재귀) |
| 활용 문제 | 최단거리, 퍼즐 탐색 | 경로 찾기, 백트래킹 |
두 방법 모두 필수적이지만, 문제의 성격에 따라 적절히 선택해야 한다.
BFS 실전 적용 시 주의사항
- 방문 체크는 큐에 넣을 때 해야 한다. 꺼낼 때 하면 중복 방문이 발생할 수 있다.
- 상태를 복합적으로 관리해야 하는 경우, 예를 들어 벽을 부수는 횟수나 특정 상태를 함께 추적해야 할 때는
(위치, 추가 상태)처럼 복합 데이터를 큐에 넣는다. - 가중치가 다를 경우 일반 BFS 대신 다익스트라(Dijkstra) 알고리즘을 사용해야 한다.
BFS는 컴퓨터 과학과 알고리즘 분야에서 가장 기본이면서도 강력한 탐색 기법이다. 탐색 문제를 푸는 데 있어 기본기로 삼아야 하며, 다양한 변형과 함께 연습해야 실전에 강해질 수 있다.
답글 남기기