전역 플래너가 푸는 문제는 이렇게 적혀요. 입력은 점유 격자, 지도를 같은 크기의 칸으로 잘라 각 칸이 갈 수 있는지 아닌지를 담은 2차원 배열이에요. 여기에 시작 칸과 목표 칸이 주어지고, 출력은 장애물을 피해 둘을 잇는 비용 최소의 칸 나열이에요. 로봇이 실제로 움직이는 건 이 나열을 받은 컨트롤러의 일이고, 플래너는 어느 칸들을 지날지까지만 답해요.
대각선을 1로 치면 경로가 흔들려요
첫 설계 결정은 이웃의 정의예요. 상하좌우 4개로 볼지, 대각선까지 8개로 볼지요. 4방은 경로가 계단처럼 꺾이는 대신 구현이 단순하고, 8방은 자연스러운 대신 처리할 게 하나 늘어요.
대각 한 스텝의 실거리는 한 변이 1일 때 약 1.414예요. 이걸 귀찮다고 1로 치면 대각 이동이 가로 1 + 세로 1을 반값에 가는 할인 이동이 돼요. 플래너는 싼 쪽을 고르니 경로가 필요도 없는 대각 흔들림으로 가득 차요.
| 이동 | 칸 변화 | 스텝 비용 |
|---|---|---|
| 직선 | 행 또는 열만 ±1 | 1 |
| 대각 | 행·열 둘 다 ±1 | √2 ≈ 1.414 |
이웃을 나열하는 코드는 어느 탐색이든 똑같이 생겼어요. 방향 배열을 돌며 경계와 장애물을 검사하는 것뿐이라, 이 조각을 손에 익히면 코드의 절반이 끝나요.
const int dr[4] = {-1, 1, 0, 0}; // 상, 하, 좌, 우의 행 변화
const int dc[4] = {0, 0, -1, 1};
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; // 격자 밖
if (grid[nr][nc] == '#') continue; // 장애물
// (nr, nc)가 유효한 이웃
}좌표 주의가 하나 있어요. 배열 인덱스는 행이 먼저인데 지도 좌표는 x가 먼저라, 실전에서 둘이 섞이면 경로가 90도 뒤집히는 버그가 나요.
꺼낸 순간이 확정되는 순간
다익스트라는 시작점에서 지금까지 든 비용이 가장 작은 칸부터 차례로 확정해 나가는 탐색이에요. 칸마다 여기까지의 최소 비용을 관리하고, 아직 확정 안 된 칸 중 그 값이 가장 작은 것을 최소 힙에서 꺼내요. 꺼낸 칸의 이웃마다 “이 칸을 거쳐 가면 더 싼가”를 물어 싸지면 갱신해요.
지형마다 통과 비용이 다른 지도를 생각하면 감이 잡혀요. 포장로 1, 잔디 3, 자갈 9. 최단 스텝 수가 아니라 비용 합이 최소인 경로를 찾아야 해요.
while (!pq.empty()) {
auto [d, r, c] = pq.top(); pq.pop(); // 지금 가장 싼 후보
if (d > dist[r][c]) continue; // 낡은 항목 — 더 싼 걸 이미 앎
if (r == tr && c == tc) return d; // 목표를 꺼냈다 = 최단 확정
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i], nc = c + dc[i];
if (/* 경계·장애물 검사 */) continue;
int nd = d + (terrain[nr][nc] - '0'); // 이웃 칸 진입 비용
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
pq.push({nd, nr, nc});
}
}
}왜 “큐에서 꺼낸 순간 확정”이라고 말할 수 있는지가 이 알고리즘의 심장이에요. 꺼낸 칸의 비용보다 싼 경로가 나중에 발견될 수는 없어요. 큐에 남은 모든 후보의 비용이 그 이상이고, 칸 비용에 음수가 없으니 거기서 어디로 더 가 봐야 비용은 늘기만 하거든요. 그래서 목표를 꺼내는 순간 바로 반환해도 됩니다.
코드에 관용구가 하나 숨어 있어요. 표준 우선순위 큐에는 이미 들어 있는 항목의 키를 낮추는 기능이 없어서, 더 싼 경로를 찾으면 같은 칸을 그냥 새로 넣어요. 그러면 한 칸이 큐에 여러 번 들어가는데, 꺼냈을 때 낡은 항목이면 건너뛰어요. 이 두 줄이 실무 다익스트라의 표준 형태입니다. 검사를 빼먹으면 답은 대체로 맞는데 같은 칸을 여러 번 확장해서 큰 지도에서 시간이 눈에 띄게 늘어요.
너비 우선 탐색과의 관계도 여기서 정리돼요. 모든 스텝 비용이 1로 균일하면 큐에서 나오는 순서가 들어간 순서와 같아져서 우선순위 큐가 일반 큐처럼 동작해요. 그 특수형이 너비 우선 탐색이에요. 반대로 칸마다 비용이 다르면 너비 우선은 틀려요. 스텝 수는 적지만 자갈밭을 가로지르는 경로를 최단이라고 우기게 되거든요.
A*는 정렬 키에 한 항을 더한 것
다익스트라의 낭비를 보면 A*가 왜 나왔는지 보여요. 다익스트라는 방향 감각이 없어요. 목표가 복도 동쪽 끝인데 시작점 서쪽의 방들도 똑같이 공평하게 팝니다. 지도가 수천 칸이면 이 낭비가 그대로 계산 시간이 되고, 목표가 바뀔 때마다 재계획하는 플래너에서는 주기마다 그 값을 치러요.
A*는 큐의 정렬 키를 f = g + h로 바꿔요. g는 지금까지 든 비용, h는 그 칸에서 목표까지 남은 비용의 추정치예요. 큐가 f 순으로 정렬되니 같은 g라도 목표에서 먼 칸은 뒤로 밀리고 목표 쪽부터 파게 돼요.
if (ng < gcost[nr][nc]) {
gcost[nr][nc] = ng;
pq.push({ng + h(nr, nc), ng, nr, nc}); // 다익스트라와 다른 유일한 줄
}h를 전부 0으로 두면 곧 다익스트라예요. 둘은 다른 알고리즘이 아니라 h가 있느냐의 차이이고, 이 사실이 플래너 소스를 읽는 열쇠가 됩니다.
휴리스틱은 둘이 표준이에요. 4방이면 맨해튼 거리, 8방이나 연속 공간이면 유클리드 거리요. 공통점은 전부 장애물을 무시한 이상적 거리라는 것 — 그래서 실제 남은 비용보다 클 수가 없어요.
그 성질에 이름이 있어요. 허용 가능(admissible), 즉 h가 실제 남은 최소 비용을 절대 과대평가하지 않는다는 조건이에요. 이게 지켜져야 최단이 보장되는 이유는 목표를 꺼내는 순간을 보면 돼요. 목표 칸의 h는 0이니 꺼낸 f가 곧 실제 비용이고, 큐에 남은 후보의 f는 각자를 거쳐 가는 진짜 최단보다 작거나 같아요. 그러니 남은 걸 마저 파도 더 싸질 수 없어요.
일부러 부풀리면 속도와 최단을 맞바꿔요
반대편이 흥미로워요. h를 일부러 부풀리면, 즉 f = g + w·h로 1보다 큰 가중치를 곱하면 탐색이 목표를 향해 더 곧장 파고들어 확장하는 칸 수가 급감해요. 빨라진다는 뜻이에요.
대신 보장이 깨져요. 실제로는 최단 경로 위에 있는 칸인데 부풀린 h 때문에 큐 뒤로 밀리고, 그 사이 조금 더 비싼 경로가 먼저 목표에 닿아 답으로 확정될 수 있어요. 알려진 성질은 원래 h가 허용 가능하면 결과가 최단의 w배 이내라는 것까지예요. 최단은 포기하되 얼마나 나빠질지 상계는 갖는 거래이고, 지도가 크고 재계획이 잦은 실전 플래너들이 이 다이얼을 일부러 돌려요.
위험한 건 모르고 하는 과대평가예요. 전형이 8방 격자에 맨해튼 휴리스틱을 그대로 쓰는 실수입니다. 대각 한 스텝의 실거리는 1.41인데 맨해튼은 그 이동을 2로 추정하니 과대평가죠. 컴파일 에러도 크래시도 없이 경로만 가끔 설명하기 어렵게 돌아요. “탐색은 도는데 경로가 최단이 아니다” 증상이면 휴리스틱과 스텝 비용의 짝이 맞는지부터 봐야 해요.
경로는 칸마다 한 칸씩만 기록하면 나와요
지금까지 코드는 비용이라는 숫자 하나만 돌려줬어요. 필요한 건 경로 자체예요. 탐색 중에 경로 전체를 칸마다 복사해 들고 다니면 비용이 경로 길이만큼 곱으로 붙으니, 대신 각 칸에 “어디에서 왔는가” 하나만 기록해요.
기록하는 자리는 정해져 있어요. 비용을 갱신하는 바로 그 줄이에요. 이 칸까지의 최단이 어느 칸 경유로 갱신됐다는 사실이 곧 직전 칸이 누구인지거든요. 더 싼 경로가 나타날 때마다 덮어쓰면, 탐색이 끝난 뒤 각 칸에는 최단 경로의 직전 칸만 남아요. 전체를 그려 보면 시작점을 뿌리로 하는 트리가 만들어진 거예요.
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
came_from[{nr, nc}] = {r, c}; // "여기는 (r,c)에서 왔다"
pq.push({nd, nr, nc});
}
// 탐색이 끝난 뒤 — 목표에서 시작까지 거꾸로 걷고 뒤집는다
while (cur != start) { path.push_back(cur); cur = came_from.at(cur); }
path.push_back(start);
std::reverse(path.begin(), path.end());경로가 목표에서 시작 방향으로 자라니 마지막 뒤집기를 빼먹으면 로봇이 경로를 반대로 받는 셈이 돼요. 목표가 기록에 아예 없으면 탐색이 거기 도달하지 못했다는 뜻이라 경로 없음으로 처리해야 하고요.
코스트맵 위에서 돌리면 그게 플래너예요
지금까지 장애물은 못 가는 칸 하나였어요. 실제 지도는 더 섬세해요. 벽 자체는 못 가지만, 벽에서 10cm 떨어진 칸은 갈 수는 있는데 되도록 피하고 싶은 칸이거든요. 이 꺼려지는 정도를 칸마다 숫자로 적은 게 코스트맵이에요.
플래너 입장에서 반영은 한 줄 수정이에요.
int nd = d + 1; // 균일 격자: 이동 거리만
int nd = d + 1 + costmap[nr][nc]; // 코스트맵 위: 거리 + 들어가는 칸의 위험이렇게 바꾸면 가장 짧은 경로가 아니라 이동 거리와 위험의 합이 가장 싼 경로를 찾아요. 벽에 붙은 지름길 대신 방 가운데로 도는, 시각화에서 보는 그 경로요.
그리고 이게 기본 전역 플래너의 실체예요. 코스트맵 비용 위에서 다익스트라를 돌려 전 칸의 비용 배열을 만들고, 목표에서 값이 낮아지는 내리막을 따라 시작까지 내려가 경로를 뽑아요. 기본이 다익스트라이고 옵션 하나를 켜면 A*로 바뀌는데, “h의 유무 차이일 뿐”이라는 관찰이 소스에서는 옵션 분기 하나로 나타나는 거예요.
격자 경로에는 태생적 흠이 하나 남아요. 이동 방향이 4개나 8개뿐이라 실제 직선을 계단으로 근사하고, 꺾이는 지점마다 각진 모서리가 생겨요. 로봇이 그대로 따라가면 모서리마다 감속과 회전을 반복해 주행이 흔들려요. 그래서 전역 경로 뒤에는 시야가 트인 중간 칸을 건너뛰거나 곡선으로 보간하는 후처리가 붙습니다. 격자 경로는 다듬어서 쓰는 재료예요.
경로를 실제로 따라가는 쪽 이야기는 경로 추종의 전방 주시 거리와 이탈 오차의 최적점에 있어요. 여기서 만든 칸 나열을 받아 속도 명령으로 바꾸는 층이에요.