꺼내는 순서를 큐가 아니라 비용이 정한다

늪은 지나는 데 3, 포장된 길은 1이 듭니다. 이런 맵에서 가장 빠른 길은 칸을 적게 밟는 길이 아니라 비용의 합이 작은 길입니다. 두 칸짜리 늪길이 여섯 칸짜리 우회로보다 비쌀 수 있습니다.

걸음 수를 세는 탐색은 여기서 답을 틀립니다. 한 걸음이 전부 같은 한 걸음이 아니니까요. 고치는 방법은 하나입니다. 꺼내는 순서를 넣은 차례가 아니라 지금까지 든 비용이 정하게 만드는 것입니다. 이 방식에 붙은 이름이 다익스트라 알고리즘(Dijkstra’s algorithm) 입니다.

비용이 가장 적은 후보부터 확정한다

절차는 그대로입니다. 후보를 담아 두고, 하나 꺼내 확정하고, 그 이웃을 다시 담습니다. 담아 두는 자리가 우선순위 큐로 바뀌고, 담을 때 그 정점까지 든 비용을 같이 넣는 것만 다릅니다.

G 를 보면 이 알고리즘이 하는 일이 드러납니다. 걸음 수로는 S 에서 B 를 거쳐 두 걸음이면 닿습니다. 그런데 그 길은 비용이 10입니다. A 와 C 를 거치는 세 걸음짜리 길이 비용 5로 더 쌉니다. 확정되는 값은 5입니다.

중간에 이미 확정된 정점이 다시 꺼내졌다가 버려지는 장면이 나옵니다. 더 싼 길을 나중에 찾아서 같은 정점을 한 번 더 넣었기 때문입니다. 꺼낼 때 확정 여부만 보고 버리면 됩니다.

한 번 확정하면 다시 안 본다

우선순위 큐에서 꺼낸 정점의 비용은 그 자리에서 최종값이 됩니다. 나중에 더 싼 길이 나타날 걱정을 안 합니다.

근거는 한 줄입니다. 모든 간선의 비용이 0 이상이기 때문입니다. 지금 꺼낸 후보가 5인데 이보다 싸게 그 정점에 닿으려면, 아직 확정 안 된 어떤 정점을 거쳐야 합니다. 그런데 그 정점은 큐에 5보다 큰 값으로 들어 있고, 거기서 간선을 하나 더 타면 비용은 더 커지기만 합니다. 5보다 싼 길은 존재할 수 없습니다.

그래서 매 단계 “지금 가장 싼 후보” 를 고르는 것만으로 최적해가 나옵니다. 되돌아가서 고치는 절차가 없습니다.

코드

var dist = new Dictionary<int, float>();
var parent = new Dictionary<int, int>();
var pq = new MinHeap<(float cost, int node)>();

dist[start] = 0f;
pq.Push((0f, start));

while (pq.Count > 0) {
    var (cost, cur) = pq.Pop();

    if (cost > dist[cur]) continue;          // 낡은 항목이라 버린다
    if (cur == goal) break;                  // 목표를 확정했으면 끝

    foreach (var (next, w) in Neighbors(cur)) {
        float nd = cost + w;
        if (dist.TryGetValue(next, out float old) && old <= nd) continue;

        dist[next] = nd;
        parent[next] = cur;
        pq.Push((nd, next));
    }
}

cost > dist[cur] 한 줄이 낡은 항목을 거릅니다. 같은 정점을 더 싼 값으로 다시 넣었을 때, 먼저 들어간 비싼 항목이 나중에 꺼내집니다. 그때 버리면 됩니다. 우선순위 큐에는 이미 들어간 값을 수정하는 기능이 없어서 쓰는 방법입니다.

목표 하나만 필요하면 그 정점을 확정하는 순간 멈춥니다. 나머지를 확정할 이유가 없습니다. 반대로 모든 칸까지의 거리 지도가 필요하면 큐가 빌 때까지 돌립니다.

음수 간선이 있으면 무너진다

“확정하면 다시 안 본다” 는 모든 간선이 0 이상일 때만 성립합니다. 하나라도 음수면 근거가 깨집니다.

S --5--> A
|        |
2       -4
v        v
B ------> G

S 에서 B 가 2라 먼저 확정됩니다. 그런데 A 를 거쳐 오는 길에 비용 -4 짜리 간선이 있으면 나중에 더 싼 값이 나타납니다. 이미 확정해 버린 뒤라 고칠 기회가 없습니다.

게임에서 음수 비용을 쓰고 싶어지는 자리가 있습니다. 지름길이나 순간이동, 이동하면 마나가 차는 지형 같은 것들입니다. 그걸 음수 간선으로 모델링하지 마세요. 비용을 전부 양수로 옮기거나, 자원 회복은 비용이 아닌 다른 축으로 다루는 편이 낫습니다. 음수가 꼭 필요하면 다른 알고리즘을 써야 합니다.

비용이 전부 같으면 큐 하나로 충분하다

간선 비용이 전부 1이면 다익스트라의 확정 순서는 걸음 수 순서와 똑같아집니다. 답도 같습니다. 그럴 때는 우선순위 큐를 쓸 이유가 없습니다. 넣은 순서대로 꺼내는 큐가 더 싸고 단순합니다.

셋을 가르는 기준은 비용이 다른가와 목표가 하나인가 둘뿐입니다.

게임에서 가중치를 어디서 얻나

비용은 지형에서만 오지 않습니다. 같은 알고리즘에 다른 숫자를 넣으면 다른 행동이 나옵니다.

“어떻게 갈까” 를 코드로 짜는 대신 “무엇이 비싼가” 를 정하면 되는 것이 이 방식의 값어치입니다. 숨는 AI 와 돌격하는 AI 를 가중치 표 두 개로 만들 수 있습니다.

비용이 실시간으로 바뀌는 경우는 조심해야 합니다. 적이 움직일 때마다 위험 지도가 바뀌는데, 프레임마다 전체를 다시 돌리면 감당이 안 됩니다. 몇 프레임에 한 번 갱신하거나, 바뀐 구역만 다시 계산하는 쪽으로 정해야 합니다.

비용

정점 수를 V, 간선 수를 E 라고 하면 O(E log V) 입니다. 간선마다 한 번씩 우선순위 큐에 넣을 수 있고, 넣고 꺼내는 데 각각 log V 가 들기 때문입니다.

격자에서는 칸 하나가 정점이고 이웃이 넷이라 간선이 정점의 두 배 정도입니다. 100 곱하기 100 짜리 맵이면 정점 1만, 간선 2만입니다. 큐 연산이 log 1만, 즉 열네 번쯤이니 수십만 번의 연산입니다. 한 번 계산하는 것은 괜찮고, 매 프레임 여러 유닛이 각자 돌리는 것은 안 됩니다.

정리

다익스트라 알고리즘은 비용이 가장 적은 후보부터 확정하는 방식입니다. 담아 두는 자리를 우선순위 큐로 바꾸고 비용을 같이 넣은 것이 전부입니다.

• 한 번 확정하면 고치지 않습니다. 간선 비용이 0 이상이면 그보다 싼 길이 존재할 수 없기 때문입니다
• 음수 간선이 하나라도 있으면 그 근거가 깨집니다. 게임에서 회복이나 지름길을 음수로 모델링하지 마세요
• 우선순위 큐에 낡은 항목이 남으므로 꺼낼 때 cost > dist[cur] 로 거릅니다
• 비용이 전부 같으면 큐 하나로 충분합니다. 우선순위 큐는 비용이 다를 때만 값을 합니다
• 비용에 무엇을 넣느냐가 곧 AI 의 성격이 됩니다. 위험도를 넣으면 돌아가고, 높이를 넣으면 완만한 길로 갑니다