---
title: "가까운 곳부터 한 겹씩 퍼지면 그게 곧 최단 거리다"
description: "너비 우선 탐색은 꺼내는 자리를 스택에서 큐로 바꾼 것이 전부입니다. 그 하나가 왜 최단 거리를 보장하는지, 거리와 부모를 어떻게 기록해 경로를 되짚는지, 그리고 칸마다 비용이 달라지면 왜 무너지는지."
author: "유니얼"
pubDate: 2026-09-15
updatedDate: 2026-09-18
category: "programming/algorithm/graph"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-bfs/
---
턴제 게임에서 유닛을 고르면 갈 수 있는 칸이 파랗게 표시됩니다. 이동력이 3이면 세 걸음 안에 닿는 칸만 칠해야 합니다.
적이 플레이어를 쫓을 때도 마찬가지입니다. 아무 길이나가 아니라 **가장 짧은 길**로 와야 합니다.

두 문제 모두 "어디까지 이어져 있나" 가 아니라 "몇 걸음이면 닿나" 를 묻습니다.
갈 곳을 담아 두고 하나씩 꺼내 훑는 절차는 그대로 두고, **꺼내는 자리만 바꾸면** 이 질문에 답할 수 있습니다.

## 한 겹씩 퍼진다

담아 두는 자리를 큐로 바꿉니다. 큐는 먼저 넣은 것이 먼저 나옵니다.
시작 정점의 이웃을 전부 넣었으니 그것들이 먼저 나오고, 그다음에야 이웃의 이웃이 나옵니다.
**한 걸음 거리를 전부 방문한 뒤에 두 걸음 거리로 넘어갑니다.**
이것이 **너비 우선 탐색(BFS, breadth-first search)** 입니다.

<x-traverse>
<script type="application/json">
{
  "label": "꺼내는 자리를 바꿔 보기",
  "nodes": [
    { "id": "S", "x": 0, "y": 90 },
    { "id": "A", "x": 115, "y": 15 },
    { "id": "B", "x": 115, "y": 165 },
    { "id": "C", "x": 235, "y": 15 },
    { "id": "D", "x": 235, "y": 175 },
    { "id": "G", "x": 355, "y": 90 }
  ],
  "edges": [["S", "A"], ["S", "B"], ["A", "C"], ["C", "G"], ["B", "G"], ["B", "D"]],
  "start": "S",
  "modes": ["bfs", "dfs"],
  "note": "강조된 간선이 그 정점에 실제로 닿은 길입니다"
}
</script>
</x-traverse>

G 를 보면 차이가 드러납니다. 큐로 돌리면 B 를 거쳐 **두 걸음**에 닿고, 스택으로 돌리면 A 와 C 를 거쳐 **세 걸음**에 닿습니다.
둘 다 G 를 찾아내지만 찾아낸 길이 다릅니다. 스택 쪽은 먼저 파고든 갈래에서 나온 길일 뿐 짧은 길이라는 보장이 없습니다.

## 코드는 스택을 큐로 바꾼 것이 전부다

```csharp
var queue = new Queue<int>();
visited[start] = true;
queue.Enqueue(start);

while (queue.Count > 0) {
    int cur = queue.Dequeue();
    Visit(cur);

    foreach (int next in adj[cur]) {
        if (visited[next]) continue;
        visited[next] = true;
        queue.Enqueue(next);
    }
}
```

한 군데가 더 다릅니다. **표시를 꺼낼 때가 아니라 넣을 때 찍습니다.**

큐에서는 이게 정석입니다. 같은 정점이 여러 이웃에게서 동시에 발견되는 일이 흔한데,
넣을 때 표시하면 큐에 한 번만 들어갑니다. 꺼낼 때 표시하면 같은 정점이 큐에 여러 벌 쌓입니다.
격자처럼 이웃이 사방에 있는 그래프에서는 이 차이가 메모리로 바로 나타납니다.

넣을 때 찍어도 방문 순서가 어긋나지 않는 이유가 있습니다.
**어차피 처음 넣은 그 자리가 가장 짧은 길**이라, 나중에 다른 이웃이 같은 정점을 다시 발견해도 넣을 이유가 없습니다.

## 왜 최단 거리가 보장되는가

큐에 들어가는 순서를 따라가면 보입니다.

1. 시작 정점이 먼저 들어갑니다. 거리 0입니다
2. 거리 0을 꺼내면서 그 이웃이 들어갑니다. 전부 거리 1입니다
3. 거리 1을 전부 꺼낸 뒤에야 거리 2가 나옵니다

큐 안에는 **거리가 같거나 하나 차이 나는 정점만** 들어 있고, 순서가 뒤집히지 않습니다.
그래서 어떤 정점을 처음 만났을 때의 거리가 그 정점까지의 최단 거리입니다.
나중에 다른 경로로 같은 정점에 닿아 봐야 그 경로는 더 길거나 같습니다.

**단, 모든 간선의 비용이 같을 때만입니다.** 한 걸음이 전부 똑같이 한 걸음이어야 "걸음 수 = 거리" 가 성립합니다.

## 거리와 경로를 같이 기록한다

방문 여부만 기록하면 "닿는다" 까지만 압니다. 몇 걸음인지와 어느 길로 왔는지는 배열 두 개를 더 두면 나옵니다.

```csharp
var dist = new int[n];
var parent = new int[n];
Array.Fill(dist, -1);
Array.Fill(parent, -1);

dist[start] = 0;
queue.Enqueue(start);

while (queue.Count > 0) {
    int cur = queue.Dequeue();

    foreach (int next in adj[cur]) {
        if (dist[next] != -1) continue;   // 이미 더 짧은 길로 닿았다
        dist[next] = dist[cur] + 1;
        parent[next] = cur;
        queue.Enqueue(next);
    }
}
```

`dist` 가 방문 표시를 겸합니다. -1 이면 아직 못 간 정점이고, 값이 있으면 그 값이 최단 거리입니다.
따로 `visited` 를 두면 두 배열이 어긋날 자리가 생기므로 하나로 두는 편이 낫습니다.

경로는 도착점에서 거꾸로 따라갑니다.

```csharp
var path = new List<int>();
for (int at = goal; at != -1; at = parent[at])
    path.Add(at);
path.Reverse();
```

`parent` 는 그 정점에 처음 닿게 해 준 정점입니다. 처음 닿은 길이 최단이므로 거꾸로 따라가면 최단 경로가 나옵니다.
경로를 안 쓸 거라면 `parent` 는 만들지 않아도 됩니다. 이동 범위 표시처럼 거리만 필요한 경우가 그렇습니다.

## 이동력 3칸을 칠하는 코드

거리를 알고 있으니 범위 표시는 조건 하나입니다.

```csharp
if (dist[next] > moveRange) continue;   // 이동력 밖이면 더 퍼뜨리지 않는다
```

여기서 중요한 것은 **칠하지 않는 것이 아니라 퍼뜨리지 않는 것**입니다.
이동력 밖의 칸을 큐에 넣지 않으면 그 너머는 아예 보지 않습니다.
맵이 200 곱하기 200 이어도 이동력이 3이면 실제로 훑는 칸은 수십 개입니다.

목표 하나를 찾는 경우도 같습니다. 꺼낸 정점이 목표면 그 자리에서 멈춥니다.
큐가 빌 때까지 돌리면 맵 전체를 훑게 되는데, 최단 거리는 이미 그 순간 확정돼 있습니다.

## 여러 곳에서 동시에 퍼뜨리기

시작점을 하나만 넣어야 할 이유는 없습니다. 이렇게 쓰는 방식을 멀티 소스 BFS 라고 부릅니다. **여러 정점을 거리 0으로 큐에 미리 넣으면** 그 모두에서 동시에 퍼집니다.
각 칸에는 가장 가까운 시작점까지의 거리가 남습니다.

```csharp
foreach (var enemy in enemies) {
    dist[Index(enemy)] = 0;
    queue.Enqueue(Index(enemy));
}
```

한 번 돌리면 맵 전체에 "가장 가까운 적까지 몇 칸인가" 가 채워집니다.
적 수만큼 따로 돌릴 필요가 없고 비용도 한 번 훑는 것과 같습니다.

이 한 장이 쓰이는 자리가 여럿입니다.

| 무엇을 시작점으로 | 나오는 것 | 쓰임 |
| --- | --- | --- |
| 적 전부 | 가장 가까운 적까지의 거리 | 위험 지도. 낮은 칸을 피해 도망 경로를 고른다 |
| 불붙은 칸 전부 | 불이 번지는 데 걸리는 턴 | 확산 시뮬레이션 |
| 출구 전부 | 출구까지의 거리 | 어느 칸에서든 한 번 읽어 방향을 정한다 |

마지막 줄이 특히 셉니다. 유닛마다 길찾기를 돌리는 대신 **지도를 한 번 만들어 두고 모두가 읽습니다.**
유닛이 늘어도 길찾기 비용이 안 늘어납니다.

## 칸마다 비용이 다르면 무너진다

너비 우선 탐색이 세는 것은 걸음 수입니다. 늪이든 포장도로든 한 칸은 한 칸입니다.

<x-compare>
<script type="application/json">
{
  "tabs": [
    {
      "label": "모든 칸이 같다",
      "text": "가로지르는 길이 네 칸, 우회로가 여섯 칸입니다. 너비 우선 탐색은 네 칸짜리를 고르고, 그것이 실제로 가장 빠릅니다.",
      "stats": [["고른 길", "4칸"], ["실제 비용", "4"], ["가장 싼 길", "4"]],
      "tone": "good"
    },
    {
      "label": "늪은 세 배 느리다",
      "text": "같은 지도인데 가로지르는 길의 두 칸이 늪이라 비용이 3씩입니다. 네 칸짜리 길은 비용 8이 되고 여섯 칸짜리 우회로가 비용 6으로 더 쌉니다. 그래도 너비 우선 탐색은 네 칸짜리를 고릅니다.",
      "stats": [["고른 길", "4칸"], ["실제 비용", "8"], ["가장 싼 길", "6"]],
      "tone": "bad"
    }
  ]
}
</script>
</x-compare>

답이 틀리는 이유는 간단합니다. 큐는 **넣은 순서**로 꺼냅니다. 비용을 모릅니다.
비싼 칸을 한 걸음으로 세는 순간 "먼저 닿은 것이 가장 싸다" 가 깨집니다.

고치려면 꺼내는 자리를 한 번 더 바꿔야 합니다. 넣은 순서가 아니라 **지금까지 든 비용이 가장 적은 것**부터 꺼내면 됩니다.
그렇게 꺼내는 자리가 우선순위 큐이고, 그 방식이 다익스트라입니다.
비용이 전부 같은 그래프에서는 둘이 같은 답을 내므로, 그때는 큐 하나로 충분합니다.

## 정리

너비 우선 탐색은 깊이 우선 탐색에서 **꺼내는 자리를 스택에서 큐로 바꾼 것**입니다.
그 하나 때문에 가까운 정점부터 한 겹씩 퍼지고, 처음 닿은 순간의 거리가 곧 최단 거리가 됩니다.

쓸 때 챙길 것은 셋입니다.

- **표시는 큐에 넣을 때 찍습니다.** 꺼낼 때 찍으면 같은 정점이 큐에 여러 벌 쌓입니다
- **`dist` 배열 하나가 방문 표시와 거리를 겸합니다.** -1 이면 못 간 곳, 값이 있으면 그 값이 최단 거리입니다. 경로가 필요하면 `parent` 를 같이 적어 두고 거꾸로 따라갑니다
- **모든 간선의 비용이 같아야 성립합니다.** 늪이나 언덕처럼 칸마다 비용이 다르면 걸음 수와 실제 비용이 어긋납니다

시작점을 여러 개 넣어도 되고, 그러면 한 번 돌려서 맵 전체에 "가장 가까운 무엇까지의 거리" 를 채울 수 있습니다.
유닛마다 길찾기를 돌리던 것을 지도 한 장으로 바꾸는 방법입니다.