BFS 문제 풀이 패턴 정리에서 가장 중요한 것은 구현법보다 문제를 보는 눈입니다. queue를 어떻게 쓰는지는 금방 익힐 수 있지만, 어떤 문제에서 BFS를 떠올려야 하는지는 훨씬 더 자주 막히기 때문입니다.
이번 글에서는 BFS를 “그래프 탐색 알고리즘 하나”로 설명하는 대신, 최단거리, 레벨 탐색, 상태 전이 문제에서 어떤 신호가 보이면 BFS를 써야 하는지를 중심으로 더 자세하게 정리하겠습니다. 이번 보강판에서는 레벨 확장 그림과 신호 카드도 같이 넣었습니다.
BFS를 가장 먼저 떠올려야 하는 경우
- 가중치가 없는 그래프에서 최단거리를 구한다
- 한 번의 이동이 모두 같은 비용이다
- 시작점에서 한 칸씩 퍼져 나가는 그림이 그려진다
- 현재 상태에서 다음 상태로 이동하는 규칙이 분명하다
즉 BFS는 단순 그래프보다 “같은 비용으로 한 층씩 확장되는 문제”에 더 강하게 반응하는 알고리즘입니다. 격자, 미로, 숨바꼭질, 전염 시뮬레이션 같은 문제에서 특히 이 감각이 자주 등장합니다.
왜 최단거리 문제와 잘 맞을까
BFS는 먼저 들어간 상태를 먼저 꺼내는 queue 구조를 쓰기 때문에, 가까운 거리부터 차례대로 탐색하게 됩니다. 그래서 어떤 정점이나 칸에 처음 도착했을 때의 거리가 곧 최단거리라는 성질이 생깁니다.
from collections import deque
def bfs(start):
q = deque([start])
dist[start] = 0
while q:
now = q.popleft()
for nxt in graph[now]:
if dist[nxt] == -1:
dist[nxt] = dist[now] + 1
q.append(nxt)이 코드에서 핵심은 queue 문법이 아니라, dist 배열이 거리 레벨을 한 층씩 기록한다는 점입니다. visited만 두고 distance를 별도로 관리하지 않으면 “몇 번 만에 갔는가”를 놓치기 쉽습니다.
코딩테스트에서 자주 나오는 BFS 패턴
- 격자 최단거리 탐색
- 여러 시작점이 동시에 퍼지는 문제
- 정점 수가 적당하고 이동 규칙이 일정한 상태 전이 문제
- 레벨별 처리나 날짜/시간이 한 단계씩 증가하는 시뮬레이션 문제
이런 패턴은 겉으로는 그래프가 아닐 수도 있지만, 상태를 정점으로 보면 BFS 구조로 바뀌는 경우가 많습니다. 그래서 그래프 그림이 안 보여도 “상태를 한 칸씩 이동한다”는 신호가 있으면 BFS를 생각해 볼 만합니다.
자주 하는 오해
- 최단거리면 무조건 BFS라고 생각하는 것
- 가중치가 있는 문제에도 BFS를 그대로 쓰는 것
- visited와 distance 역할을 섞어 쓰는 것
- 상태 정의가 빠진 채 좌표만 queue에 넣는 것
특히 가중치가 다르면 BFS 대신 다른 최단거리 알고리즘이 필요할 수 있습니다. 그래서 BFS를 떠올릴 때는 항상 “한 번 이동 비용이 같은가”를 먼저 보는 편이 안전합니다.
queue의 FIFO 성질은 std::queue 설명처럼 자료구조 문서로 보면 단순해 보이지만, 코딩테스트에서는 그 순서성이 거리 레벨 확장과 연결된다는 점이 더 중요합니다.
기본 BFS 설명은 기존 BFS 글과 이어 보고, queue 자료구조는 후속 덱 글과 연결할 수 있습니다.
실전에서 BFS인지 아닌지 빠르게 판별하는 법
문제를 읽으면서 “한 번 움직일 때 비용이 모두 같은가?”, “가까운 것부터 차례대로 확인해도 되나?”, “처음 도착한 값이 답이 될 수 있나?”를 먼저 체크해 보세요. 이 세 질문에 대부분 예라고 답하면 BFS 가능성이 매우 큽니다.
마무리
BFS를 잘 쓰는 사람은 queue 구현을 잘 외운 사람이 아니라, 문제에서 거리 레벨이 한 층씩 확장되는 신호를 빨리 보는 사람입니다.
즉 BFS의 핵심은 너비 우선이라는 이름보다, 같은 비용으로 퍼져 나가는 최단거리 구조를 알아보는 눈에 있습니다.
