Quick Flow
간선 비용이 모두 같을 때, 시작점에서 가까운 순서와 최소 간선 수 순서는 같습니다. 정점을 큐에 넣는 순간 방문 처리하면 첫 기록 거리가 최단 거리로 고정됩니다.
static int[] Distances(IReadOnlyList<int>[] graph, int start)
{
int[] distance = Enumerable.Repeat(-1, graph.Length).ToArray();
var queue = new Queue<int>();
queue.Enqueue(start);
distance[start] = 0;
while (queue.TryDequeue(out int current))
{
foreach (int next in graph[current])
{
if (distance[next] != -1) continue;
distance[next] = distance[current] + 1;
queue.Enqueue(next);
}
}
return distance;
}- 최소 이동 횟수 또는 무가중 그래프의 최단 거리: BFS
- 간선 비용이
0또는1: 0-1 BFS - 비용이 서로 다르고 음수가 없음: 다익스트라
구조
BFS는 시작점에서 가까운 정점부터 탐색합니다. Queue를 쓰기 때문에 먼저 발견된 정점이 먼저 처리되고, 같은 거리의 정점들이 한 층씩 확장됩니다.
거리 0: start
거리 1: start의 이웃
거리 2: 거리 1 정점의 미방문 이웃간선 비용이 모두 같다면 처음 방문한 거리가 최단 거리입니다. 방향 그래프와 무방향 그래프 모두 적용되며 시간과 공간은 O(V + E)입니다. 그래서 미로, 최소 이동 횟수, 단계별 전파 문제에 자주 사용합니다.
격자 BFS
2차원 격자는 각 칸을 정점으로 보고 상하좌우 이동을 간선으로 보면 됩니다.
static int ShortestGridDistance(
bool[,] blocked,
(int Row, int Col) start,
(int Row, int Col) goal)
{
int rows = blocked.GetLength(0);
int cols = blocked.GetLength(1);
if (blocked[start.Row, start.Col] || blocked[goal.Row, goal.Col]) return -1;
var queue = new Queue<(int Row, int Col)>();
var distance = new int[rows, cols];
var visited = new bool[rows, cols];
int[] dr = { -1, 1, 0, 0 };
int[] dc = { 0, 0, -1, 1 };
queue.Enqueue(start);
visited[start.Row, start.Col] = true;
while (queue.TryDequeue(out var current))
{
if (current == goal) return distance[current.Row, current.Col];
for (int direction = 0; direction < 4; direction++)
{
int nextRow = current.Row + dr[direction];
int nextCol = current.Col + dc[direction];
if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) continue;
if (blocked[nextRow, nextCol] || visited[nextRow, nextCol]) continue;
visited[nextRow, nextCol] = true;
distance[nextRow, nextCol] = distance[current.Row, current.Col] + 1;
queue.Enqueue((nextRow, nextCol));
}
}
return -1;
}visited를 enqueue 직전에 표시하는 부분이 핵심입니다. dequeue 뒤에 표시하면 같은 칸이 여러 부모에게서 큐에 들어갈 수 있습니다. 시작점이 여러 개면 모두 거리 0으로 표시해 큐에 넣으면, 가장 가까운 시작점에서의 거리를 한 번에 구합니다.
선택 기준
| 문제 신호 | BFS가 맞는 경우 |
|---|---|
| 최소 이동 횟수 | 간선 비용이 모두 같음 |
| 시작점에서 퍼짐 | 전파, 감염, 확산 |
| 여러 시작점 | multi-source BFS |
| 최단 경로 | 무가중 그래프 |
| 비용이 다름 | 다익스트라 검토 |
여러 시작점이 있으면 모든 시작점을 처음부터 큐에 넣고 거리 0으로 처리합니다. 목표 하나만 필요하면 목표를 처음 발견해 enqueue한 순간에도 최단 거리가 정해집니다. dequeue 시점에 멈춰도 같은 답을 얻으며, 전체 거리 배열이 필요하면 큐가 빌 때까지 진행합니다.
주의할 점
BFS는 큐에 넣을 때 방문 처리하는 편이 안전합니다. 꺼낼 때 방문 처리하면 같은 정점이 여러 번 들어갈 수 있습니다.
또 BFS가 최단 거리를 보장하는 것은 간선 비용이 모두 같을 때입니다. 비용이 다르면 우선순위 큐를 쓰는 다익스트라를 검토해야 합니다.
참고 링크
1 sources