가까운 곳부터 한 겹씩 퍼지면 그게 곧 최단 거리다

턴제 게임에서 유닛을 고르면 갈 수 있는 칸이 파랗게 표시됩니다. 이동력이 3이면 세 걸음 안에 닿는 칸만 칠해야 합니다. 적이 플레이어를 쫓을 때도 마찬가지입니다. 아무 길이나가 아니라 가장 짧은 길로 와야 합니다.

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

한 겹씩 퍼진다

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

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

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

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가 나옵니다

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

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

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

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

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 를 두면 두 배열이 어긋날 자리가 생기므로 하나로 두는 편이 낫습니다.

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

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

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

이동력 3칸을 칠하는 코드

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

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

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

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

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

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

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

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

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

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

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

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

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

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

정리

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

쓸 때 챙길 것은 셋입니다.

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

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