--- title: "꺼내는 순서를 큐가 아니라 비용이 정한다" description: "칸마다 이동 비용이 다른 맵에서 최단 경로를 찾는 다익스트라 알고리즘(Dijkstra's algorithm)입니다. 왜 한 번 확정한 것을 다시 안 봐도 되는지, 음수 간선에서 왜 무너지는지, 게임에서 가중치를 어디서 얻는지." author: "유니얼" pubDate: 2026-09-17 updatedDate: 2026-09-18 category: "programming/algorithm/graph" tags: ["탐색"] canonical: https://blog.unialgames.com/posts/algo-dijkstra/ --- 늪은 지나는 데 3, 포장된 길은 1이 듭니다. 이런 맵에서 가장 빠른 길은 **칸을 적게 밟는 길이 아니라 비용의 합이 작은 길**입니다. 두 칸짜리 늪길이 여섯 칸짜리 우회로보다 비쌀 수 있습니다. 걸음 수를 세는 탐색은 여기서 답을 틀립니다. 한 걸음이 전부 같은 한 걸음이 아니니까요. 고치는 방법은 하나입니다. **꺼내는 순서를 넣은 차례가 아니라 지금까지 든 비용이 정하게 만드는 것**입니다. 이 방식에 붙은 이름이 **다익스트라 알고리즘(Dijkstra's algorithm)** 입니다. ## 비용이 가장 적은 후보부터 확정한다 절차는 그대로입니다. 후보를 담아 두고, 하나 꺼내 확정하고, 그 이웃을 다시 담습니다. 담아 두는 자리가 우선순위 큐로 바뀌고, 담을 때 **그 정점까지 든 비용**을 같이 넣는 것만 다릅니다. G 를 보면 이 알고리즘이 하는 일이 드러납니다. **걸음 수로는 S 에서 B 를 거쳐 두 걸음이면 닿습니다.** 그런데 그 길은 비용이 10입니다. A 와 C 를 거치는 세 걸음짜리 길이 비용 5로 더 쌉니다. 확정되는 값은 5입니다. 중간에 이미 확정된 정점이 다시 꺼내졌다가 버려지는 장면이 나옵니다. 더 싼 길을 나중에 찾아서 같은 정점을 한 번 더 넣었기 때문입니다. 꺼낼 때 확정 여부만 보고 버리면 됩니다. ## 한 번 확정하면 다시 안 본다 우선순위 큐에서 꺼낸 정점의 비용은 **그 자리에서 최종값이 됩니다.** 나중에 더 싼 길이 나타날 걱정을 안 합니다. 근거는 한 줄입니다. **모든 간선의 비용이 0 이상이기 때문입니다.** 지금 꺼낸 후보가 5인데 이보다 싸게 그 정점에 닿으려면, 아직 확정 안 된 어떤 정점을 거쳐야 합니다. 그런데 그 정점은 큐에 5보다 큰 값으로 들어 있고, 거기서 간선을 하나 더 타면 비용은 더 커지기만 합니다. **5보다 싼 길은 존재할 수 없습니다.** 그래서 매 단계 "지금 가장 싼 후보" 를 고르는 것만으로 최적해가 나옵니다. 되돌아가서 고치는 절차가 없습니다. ## 코드 ```csharp var dist = new Dictionary(); var parent = new Dictionary(); 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이면 다익스트라의 확정 순서는 걸음 수 순서와 똑같아집니다. 답도 같습니다. 그럴 때는 우선순위 큐를 쓸 이유가 없습니다. **넣은 순서대로 꺼내는 큐가 더 싸고 단순합니다.** | 맵 | 무엇을 쓰나 | | --- | --- | | 모든 칸의 이동 비용이 같다 | 큐 하나. 넣은 순서가 곧 거리 순서입니다 | | 지형마다 비용이 다르다 | 우선순위 큐. 다익스트라입니다 | | 비용이 다르고 목표가 하나로 정해져 있다 | 다익스트라에 방향 감각을 더한 A 스타 | 셋을 가르는 기준은 **비용이 다른가**와 **목표가 하나인가** 둘뿐입니다. ## 게임에서 가중치를 어디서 얻나 비용은 지형에서만 오지 않습니다. 같은 알고리즘에 다른 숫자를 넣으면 다른 행동이 나옵니다. | 비용에 무엇을 넣나 | 나오는 행동 | | --- | --- | | 지형 이동 비용 (늪 3, 길 1) | 빠른 길로 간다 | | 적 근처일수록 큰 값 | 위험을 피해 돌아간다 | | 높이 차이 | 절벽을 피하고 완만한 길로 간다 | | 아군 유닛이 있는 칸에 가산 | 뭉치지 않고 흩어져 온다 | **"어떻게 갈까" 를 코드로 짜는 대신 "무엇이 비싼가" 를 정하면 되는 것**이 이 방식의 값어치입니다. 숨는 AI 와 돌격하는 AI 를 가중치 표 두 개로 만들 수 있습니다. 비용이 실시간으로 바뀌는 경우는 조심해야 합니다. 적이 움직일 때마다 위험 지도가 바뀌는데, 프레임마다 전체를 다시 돌리면 감당이 안 됩니다. 몇 프레임에 한 번 갱신하거나, 바뀐 구역만 다시 계산하는 쪽으로 정해야 합니다. ## 비용 정점 수를 V, 간선 수를 E 라고 하면 **`O(E log V)`** 입니다. 간선마다 한 번씩 우선순위 큐에 넣을 수 있고, 넣고 꺼내는 데 각각 `log V` 가 들기 때문입니다. 격자에서는 칸 하나가 정점이고 이웃이 넷이라 간선이 정점의 두 배 정도입니다. 100 곱하기 100 짜리 맵이면 정점 1만, 간선 2만입니다. 큐 연산이 log 1만, 즉 열네 번쯤이니 수십만 번의 연산입니다. **한 번 계산하는 것은 괜찮고, 매 프레임 여러 유닛이 각자 돌리는 것은 안 됩니다.** ## 정리 다익스트라 알고리즘은 **비용이 가장 적은 후보부터 확정하는 방식**입니다. 담아 두는 자리를 우선순위 큐로 바꾸고 비용을 같이 넣은 것이 전부입니다. - **한 번 확정하면 고치지 않습니다.** 간선 비용이 0 이상이면 그보다 싼 길이 존재할 수 없기 때문입니다 - 음수 간선이 하나라도 있으면 그 근거가 깨집니다. 게임에서 회복이나 지름길을 음수로 모델링하지 마세요 - 우선순위 큐에 낡은 항목이 남으므로 **꺼낼 때 `cost > dist[cur]` 로 거릅니다** - 비용이 전부 같으면 큐 하나로 충분합니다. 우선순위 큐는 비용이 다를 때만 값을 합니다 - 비용에 무엇을 넣느냐가 곧 AI 의 성격이 됩니다. 위험도를 넣으면 돌아가고, 높이를 넣으면 완만한 길로 갑니다