[CS] A* 알고리즘(최단거리 탐색 알고리즘)

 

서론

이전 글에서 다익스트라 알고리즘을 다뤘다. 다익스트라는 출발 노드로부터 모든 노드까지의 최단거리를 보장하는 강력한 알고리즘이다. 그런데 게임 AI 길찾기 상황을 생각해보자.

캐릭터가 맵의 좌측 끝에서 우측 끝으로 이동해야 한다. 다익스트라는 목적지에 도달하기 전에 출발점을 기준으로 사방으로 탐색을 퍼트린다. 맵 전체를 샅샅이 뒤지는 셈이다. 결국 목적지에 도달했을 때, 이미 탐색한 노드의 절반 이상이 "가지 않아도 될 방향"이었다는 것이다.

이 낭비를 없앨 수 없을까? "목적지가 오른쪽에 있다는 걸 알고 있으니, 왼쪽은 덜 살펴봐도 되지 않을까?" — 이 직관이 A* 알고리즘의 시작점이다.

A* 알고리즘이란?

A* 알고리즘은 출발 노드에서 목적 노드까지의 최단 경로를 찾는 알고리즘이다. 다익스트라와의 결정적 차이는 목적지 방향에 대한 추정치(휴리스틱)를 탐색 우선순위에 반영한다는 것이다.

다익스트라는 아래 기준으로 다음 탐색 노드를 결정한다:

f(n) = g(n)

g(n) : 출발점에서 현재 노드 n까지의 실제 비용

A*는 여기에 목적지까지의 추정 비용을 더한다:

f(n) = g(n) + h(n)

g(n) : 출발점 → 현재 노드까지의 실제 비용

h(n) : 현재 노드 → 목적지까지의 추정 비용 (휴리스틱)

f(n) : 이 노드를 거쳐 갈 경우의 총 예상 비용

우선순위 큐는 f(n)이 가장 낮은 노드를 먼저 꺼낸다. 즉, "지금까지 비용이 적게 들었고, 앞으로도 가까울 것 같은" 노드를 우선 탐색한다. 덕분에 다익스트라보다 훨씬 적은 노드를 탐색하고도 최단 경로에 도달할 수 있다.

핵심 아이디어 — 휴리스틱(Heuristic)

휴리스틱 h(n)은 현재 노드에서 목적지까지의 실제 비용을 정확히 알 수 없을 때 사용하는 추정 함수다. A*의 성능과 정확성은 사실상 이 h(n)에 달려 있다.

h(n)의 3가지 성질

조건	설명	결과
h(n) = 0	휴리스틱을 쓰지 않음	→ 순수 다익스트라와 동일
h(n) ≤ 실제 비용 (허용 가능한 휴리스틱)	실제 비용을 절대 과대추정하지 않음	→ 최적 해 보장
h(n) > 실제 비용	실제 비용을 과대추정	→ 빠르지만 최적 해 보장 불가

게임처럼 "완벽한 최단 경로보다 빠른 응답이 중요한" 상황에서는 의도적으로 과대추정 휴리스틱을 쓰기도 한다. 이를 Weighted A* 라 부른다.

대표 휴리스틱 함수

맨해튼 거리 — 4방향 이동(격자 맵)

h(n) = |현재.x - 목적지.x| + |현재.y - 목적지.y|

유클리드 거리 — 임의 방향 이동

h(n) = sqrt((현재.x - 목적지.x)² + (현재.y - 목적지.y)²)

체비쇼프 거리 — 8방향 이동(대각선 포함)

h(n) = max(|현재.x - 목적지.x|, |현재.y - 목적지.y|)

 

Distance functions

동작 원리 단계별 분석

A*는 두 개의 집합으로 노드를 관리한다.

• Open List : 탐색 후보 노드들 (우선순위 큐, f(n) 기준 Min Heap)
• Closed List : 이미 확정된 노드들 (재방문 방지)

단계별 흐름:

1. 시작 노드를 Open List에 삽입. g(start) = 0, f(start) = h(start)
2. Open List가 빌 때까지 반복:
   a. f(n) 최솟값 노드를 꺼낸다 (= 현재 노드)
   b. 현재 노드가 목적지면 경로 반환, 종료
   c. 현재 노드를 Closed List에 추가
   d. 인접 노드 각각에 대해:
      - Closed List에 있으면 skip
      - g(인접) = g(현재) + 이동 비용
      - f(인접) = g(인접) + h(인접)
      - Open List에 없거나, 기존 f보다 작으면 Open List에 추가/갱신
3. Open List가 비었는데 목적지 미도달 → 경로 없음

A* Sequence gif

 

다익스트라와 비교하면, 핵심 차이는 d 단계의 우선순위 계산이다. 다익스트라는 g(n)만 보지만, A*는 g(n) + h(n)을 보기 때문에 목적지 방향으로 탐색이 편향된다.

복잡도 분석

항목	다익스트라	A*
시간 복잡도	O((V + E) log V)	O(E log V) — 휴리스틱 품질에 따라 편차 큼
공간 복잡도	O(V)	O(V)
탐색 노드 수	모든 노드	휴리스틱이 좋을수록 대폭 감소
최적 해 보장	항상	h(n) ≤ 실제 비용일 때만

A의 최악 시간 복잡도는 다익스트라와 동일하다. h(n) = 0이면 문자 그대로 다익스트라이기 때문이다. 하지만  잘 만든 휴리스틱 하나가 탐색 노드를 수십 배 줄여준다는 것이 강점이다.

구현(C++)

2D 격자 맵에서의 A* 구현이다. 4방향 이동, 맨해튼 거리 휴리스틱을 적용한다.

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y;
    int g, h;
    int f() const { return g + h; }
    bool operator>(const Node& o) const { return f() > o.f(); }
};

int heuristic(int x, int y, int ex, int ey) {
    return abs(x - ex) + abs(y - ey); // 맨해튼 거리
}

// map: 0 = 이동 가능, 1 = 장애물
// 반환값: 목적지까지의 최단 비용 (-1이면 경로 없음)
int AStar(vector<vector<int>>& map, int sx, int sy, int ex, int ey) {
    int rows = map.size(), cols = map[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, INT_MAX));

    priority_queue<Node, vector<Node>, greater<Node>> openList;

    dist[sy][sx] = 0;
    openList.push({sx, sy, 0, heuristic(sx, sy, ex, ey)});

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!openList.empty()) {
        auto cur = openList.top();
        openList.pop();

        if (cur.x == ex && cur.y == ey) return cur.g;

        // 이미 더 좋은 경로로 확정된 경우 skip
        if (cur.g > dist[cur.y][cur.x]) continue;

        for (int d = 0; d < 4; d++) {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];

            if (nx < 0 || ny < 0 || nx >= cols || ny >= rows) continue;
            if (map[ny][nx] == 1) continue; // 장애물

            int ng = cur.g + 1;
            if (ng < dist[ny][nx]) {
                dist[ny][nx] = ng;
                int nh = heuristic(nx, ny, ex, ey);
                openList.push({nx, ny, ng, nh});
            }
        }
    }
    return -1; // 경로 없음
}

다익스트라 코드와 비교해보면, priority_queue에 넣는 우선순위 기준이 cost 하나에서 g + h로 바뀐 것이 전부다. 구조는 거의 동일하다.

휴리스틱 선택 기준

상황	추천 휴리스틱	이유
격자 맵, 4방향 이동	맨해튼 거리	실제 이동 방식과 일치 → 허용 가능
격자 맵, 8방향 이동	체비쇼프 거리	대각선 이동을 반영
임의 좌표 공간 (3D 등)	유클리드 거리	실제 직선 거리에 근접
속도 최우선, 최적 해 불필요	Weighted A* (w * h(n), w > 1)	탐색 편향 증가 → 빠른 근사 경로

Unreal Engine의 NavMesh 기반 길찾기도 내부적으로 A* 계열 알고리즘을 사용하며, 휴리스틱은 3D 유클리드 거리를 기반으로 한다. 단, NavMesh는 그래프 노드가 폴리곤 단위라 순수한 격자 A*보다 구조가 복잡하다.

주의사항

1. 허용 불가능한 휴리스틱 사용 시 최적 해 미보장
h(n)이 실제 비용보다 크면 목적지까지의 예상 비용을 과장하게 되어, 실제로는 더 좋은 경로를 건너뛸 수 있다. Weighted A*처럼 의도적으로 사용하는 경우가 아니라면 반드시 h(n) ≤ 실제 비용 조건을 지켜야 한다.

2. 동적으로 변하는 맵에서는 D* Lite를 고려할 것
장애물이 런타임 중 생성/소멸하는 환경(예: 전략 게임 RTS)에서는 매 프레임 A를 처음부터 재실행하면 비용이 크다. 이런 경우 경로 변경이 발생했을 때만 부분 재계산하는 D* Lite 알고리즘이 더 적합하다.

3. 메모리 폭발 주의 (대형 맵)
Open/Closed List는 최악 O(V)의 메모리를 소모한다. 대형 오픈 월드 맵에서는 계층적 A(HPA) 또는 영역 단위 분할을 사용해 메모리와 탐색 범위를 모두 줄이는 것이 일반적이다.