A* 알고리즘

A* 핵심 개념

다익스트라 + 휴리스틱

• A*는 다익스트라에 "목적지까지 얼마나 남았는지" 추정치(H)를 더한 알고리즘입니다.
• 점수:
  • G(n): 시작점 -> 현재 노드까지 실제 누적 비용
  • H(n): 현재 노드 -> 목적지까지 추정 비용(휴리스틱)
  • F(n) = G(n) + H(n): 우선순위 큐 정렬 기준

직관

• 다익스트라(H=0)는 사방으로 고르게 퍼집니다.
• A*는 H 덕분에 목적지 방향으로 탐색을 유도해 보통 더 적은 노드를 확장합니다.

최적성 전제 (중요)

• 휴리스틱이 Admissible(과대추정 금지)이면 최적 경로를 보장합니다.
  • H(n) <= 실제 최단 남은 비용
• Consistent(단조성)까지 만족하면 구현이 더 안정적입니다.
  • H(n) <= cost(n,n') + H(n')

---

휴리스틱 설계

격자 맵에서 자주 쓰는 H

이동 규칙	휴리스틱	예시
4방향(상하좌우)	맨해튼 거리	abs(dy) + abs(dx)
8방향(대각 포함)	Octile/Diagonal 거리	대각 비용 반영
연속 공간	유클리드 거리	sqrt(dx*dx + dy*dy)

스케일 맞추기

• G의 단위와 H의 단위를 맞춰야 합니다.
• 예: 직선 이동 비용을 10으로 쓰면, 맨해튼도 10 * (abs(dy)+abs(dx))로 맞춥니다.

Weighted A*

• F = G + w*H (w>1)를 쓰면 더 공격적으로 목적지로 향해 속도는 빨라질 수 있습니다.
• 단, 일반적으로 최적성 보장은 약해집니다(근사 경로 허용 시 사용).

---

오픈/클로즈드와 상태 값

• Open List: 방문 후보 집합(우선순위 큐)
• Closed Set: 확장 완료 집합
• gScore[y][x]: 현재까지 알려진 최소 실제 비용
• fScore[y][x] = gScore + heuristic
• parent[y][x]: 경로 복원용 이전 좌표

실전 포인트:

• C++ priority_queue는 decrease-key가 없으므로 더 좋은 값 발견 시 재삽입합니다.
• pop 시 "오래된 항목"은 if (node.f != fScore[y][x]) continue;로 버립니다.

---

A* 템플릿 (실전형, 4방향 격자)

struct Pos {
    int y, x;
    bool operator==(const Pos& other) const { return y == other.y && x == other.x; }
};

struct PQNode {
    int f, g;
    Pos pos;
    bool operator>(const PQNode& other) const { return f > other.f; }
};

int Heuristic(Pos a, Pos b) {
    // 4방향 + 직선비용 10 가정
    return 10 * (abs(a.y - b.y) + abs(a.x - b.x));
}

bool FindPathAStar(const vector<string>& board, Pos start, Pos dest, vector<Pos>& outPath) {
    int n = static_cast<int>(board.size());
    int m = static_cast<int>(board[0].size());
    const int INF = numeric_limits<int>::max() / 4;

    auto InRange = [&](Pos p) { return 0 <= p.y && p.y < n && 0 <= p.x && p.x < m; };
    auto CanGo = [&](Pos p) { return InRange(p) && board[p.y][p.x] != '#'; };
    if (!CanGo(start) || !CanGo(dest)) return false;

    vector<vector<int>> gScore(n, vector<int>(m, INF));
    vector<vector<int>> fScore(n, vector<int>(m, INF));
    vector<vector<bool>> closed(n, vector<bool>(m, false));
    vector<vector<Pos>> parent(n, vector<Pos>(m, Pos{-1, -1}));

    priority_queue<PQNode, vector<PQNode>, greater<PQNode>> open;

    gScore[start.y][start.x] = 0;
    fScore[start.y][start.x] = Heuristic(start, dest);
    parent[start.y][start.x] = start;
    open.push({fScore[start.y][start.x], 0, start});

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

    while (!open.empty()) {
        PQNode node = open.top();
        open.pop();

        Pos here = node.pos;
        if (closed[here.y][here.x]) continue;
        if (node.f != fScore[here.y][here.x]) continue; // 오래된 항목 스킵

        if (here == dest) break;
        closed[here.y][here.x] = true;

        for (int dir = 0; dir < 4; dir++) {
            Pos next{here.y + dy[dir], here.x + dx[dir]};
            if (!CanGo(next)) continue;
            if (closed[next.y][next.x]) continue;

            int moveCost = 10;
            int tentativeG = gScore[here.y][here.x] + moveCost;
            if (tentativeG >= gScore[next.y][next.x]) continue;

            parent[next.y][next.x] = here;
            gScore[next.y][next.x] = tentativeG;
            fScore[next.y][next.x] = tentativeG + Heuristic(next, dest);
            open.push({fScore[next.y][next.x], tentativeG, next});
        }
    }

    if (gScore[dest.y][dest.x] == INF) return false; // 도달 불가

    outPath.clear();
    for (Pos cur = dest;; cur = parent[cur.y][cur.x]) {
        outPath.push_back(cur);
        if (cur == start) break;
    }
    reverse(outPath.begin(), outPath.end());
    return true;
}

---

A* vs 다익스트라

항목	다익스트라	A*
점수	G만 사용	G + H
휴리스틱 필요	없음	필요
목적지 지향성	낮음	높음
최적성 조건	음수 간선 없음	음수 간선 없음 + 적절한 H
최악 시간복잡도	유사 (O((V+E)logV))	유사 (휴리스틱이 나쁘면 다익스트라에 가까움)

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
과대추정 휴리스틱 사용	최적 경로 보장 깨짐
G와 H 단위 불일치	탐색 품질 급락
오래된 open 항목 미스킵	연산량 급증
closed 처리 타이밍 오류	갱신 누락/오답 가능
경로 복원 전에 도달 여부 미검사	인덱스 오류/무한 루프

체크 질문 (스스로 답해보기)

• 왜 H=0이면 A*가 다익스트라가 될까?
• Admissible 휴리스틱이 최적성을 보장하는 이유는?
• 맨해튼 휴리스틱이 4방향 격자에서 적절한 이유는?
• 실무에서 A*가 체감상 빠른 이유를 탐색 노드 수 관점에서 설명할 수 있는가?

---

면접·실무 요약

• A*의 설명은 "오픈/클로즈드가 있다" 수준이 아니라, G/H/F와 휴리스틱 조건까지 말할 수 있어야 합니다.
• 우선순위 큐 없이 리스트로 open을 관리하면 성능이 크게 악화됩니다.
• 실제 게임에서는 맵 크기, 이동 규칙(4방향/8방향), 휴리스틱 품질이 성능을 좌우합니다.

---