숏컷 코드
csharp
var q = new Queue<int>();
int[] dist = Enumerable.Repeat(-1, n).ToArray();
q.Enqueue(start);
dist[start] = 0;
while (q.Count > 0)
{
int current = q.Dequeue();
foreach (int next in graph[current])
{
if (dist[next] != -1) continue;
dist[next] = dist[current] + 1;
q.Enqueue(next);
}
}구조
BFS는 시작점에서 가까운 정점부터 탐색합니다. Queue를 쓰기 때문에 먼저 발견된 정점이 먼저 처리되고, 같은 거리의 정점들이 한 층씩 확장됩니다.
text
거리 0: start
거리 1: start의 이웃
거리 2: 거리 1 정점의 미방문 이웃간선 비용이 모두 같다면 처음 방문한 거리가 최단 거리입니다. 그래서 미로, 최소 이동 횟수, 단계별 전파 문제에 자주 사용합니다.
격자 BFS
2차원 격자는 각 칸을 정점으로 보고 상하좌우 이동을 간선으로 보면 됩니다.
csharp
var q = new Queue<(int Row, int Col)>();
int[] dr = { -1, 1, 0, 0 };
int[] dc = { 0, 0, -1, 1 };
for (int dir = 0; dir < 4; dir++)
{
int nr = r + dr[dir];
int nc = c + dc[dir];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (blocked[nr, nc] || dist[nr, nc] != -1) continue;
dist[nr, nc] = dist[r, c] + 1;
q.Enqueue((nr, nc));
}선택 기준
| 문제 신호 | BFS가 맞는 경우 |
|---|---|
| 최소 이동 횟수 | 간선 비용이 모두 같음 |
| 시작점에서 퍼짐 | 전파, 감염, 확산 |
| 여러 시작점 | multi-source BFS |
| 최단 경로 | 무가중 그래프 |
| 비용이 다름 | 다익스트라 검토 |
여러 시작점이 있으면 모든 시작점을 처음부터 큐에 넣고 거리 0으로 처리합니다.
주의할 점
BFS는 큐에 넣을 때 방문 처리하는 편이 안전합니다. 꺼낼 때 방문 처리하면 같은 정점이 여러 번 들어갈 수 있습니다.
또 BFS가 최단 거리를 보장하는 것은 간선 비용이 모두 같을 때입니다. 비용이 다르면 우선순위 큐를 쓰는 다익스트라를 검토해야 합니다.
참고 링크
1 sources