A* 알고리즘 — 휴리스틱으로 탐색을 빠르게 하기

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

g(n): 시작점에서 n까지의 실제 비용
h(n): n에서 목표까지의 추정 비용 (휴리스틱)
f(n): 총 예상 비용

BFS/Dijkstra: 시작점에서 동심원처럼 전 방향 탐색
A*: 목표 방향으로 우선 탐색, 필요할 때만 다른 방향 확인

public class AStar {

    // 노드 정보
    static class Node implements Comparable<Node> {
        int x, y;
        int g; // 시작→현재 실제 비용
        int f; // g + h (총 예상 비용)

        Node(int x, int y, int g, int f) {
            this.x = x; this.y = y;
            this.g = g; this.f = f;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.f, o.f);
        }
    }

    // 4방향 이동
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    public List<int[]> findPath(int[][] grid, int[] start, int[] goal) {
        int rows = grid.length, cols = grid[0].length;
        int[][] gCost = new int[rows][cols];
        int[][] parentX = new int[rows][cols];
        int[][] parentY = new int[rows][cols];

        for (int[] row : gCost) Arrays.fill(row, Integer.MAX_VALUE);

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        boolean[][] closed = new boolean[rows][cols];

        // 시작점 초기화
        gCost[start[0]][start[1]] = 0;
        int h = heuristic(start[0], start[1], goal[0], goal[1]);
        openSet.offer(new Node(start[0], start[1], 0, h));
        parentX[start[0]][start[1]] = -1;
        parentY[start[0]][start[1]] = -1;

        while (!openSet.isEmpty()) {
            Node curr = openSet.poll();

            // 목표 도달
            if (curr.x == goal[0] && curr.y == goal[1]) {
                return reconstructPath(parentX, parentY, goal);
            }

            if (closed[curr.x][curr.y]) continue;
            closed[curr.x][curr.y] = true;

            // 이웃 탐색
            for (int d = 0; d < 4; d++) {
                int nx = curr.x + dx[d];
                int ny = curr.y + dy[d];

                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
                if (grid[nx][ny] == 1 || closed[nx][ny]) continue; // 벽이면 스킵

                int newG = curr.g + 1; // 이동 비용 1
                if (newG < gCost[nx][ny]) {
                    gCost[nx][ny] = newG;
                    int newF = newG + heuristic(nx, ny, goal[0], goal[1]);
                    openSet.offer(new Node(nx, ny, newG, newF));
                    parentX[nx][ny] = curr.x;
                    parentY[nx][ny] = curr.y;
                }
            }
        }
        return Collections.emptyList(); // 경로 없음
    }

    // 맨해튼 거리 휴리스틱
    private int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    // 경로 역추적
    private List<int[]> reconstructPath(int[][] parentX, int[][] parentY, int[] goal) {
        List<int[]> path = new ArrayList<>();
        int x = goal[0], y = goal[1];
        while (x != -1) {
            path.add(new int[]{x, y});
            int px = parentX[x][y];
            int py = parentY[x][y];
            x = px; y = py;
        }
        Collections.reverse(path);
        return path;
    }
}

h(n) ≤ 실제 비용(n → 목표)    →  최적해 보장 (admissible)
h(n) > 실제 비용              →  최적해 미보장 (하지만 더 빠를 수 있음)

// 맨해튼 거리 — 4방향 격자에 적합
int manhattan(int x1, int y1, int x2, int y2) {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}

// 유클리드 거리 — 자유로운 이동에 적합
double euclidean(int x1, int y1, int x2, int y2) {
    return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
}

// 체비셰프 거리 — 8방향 격자에 적합
int chebyshev(int x1, int y1, int x2, int y2) {
    return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
}

h(n) = 0       → Dijkstra와 동일 (가장 느림, 최적해 보장)
h(n) < 실제비용  → 적당히 빠름, 최적해 보장
h(n) = 실제비용  → 최적 (직선으로 목표까지 탐색)
h(n) > 실제비용  → 매우 빠르지만 최적해 미보장

// IDA* 개념적 구현
public int idaStar(int[] start, int[] goal) {
    int threshold = heuristic(start[0], start[1], goal[0], goal[1]);

    while (true) {
        int result = dfsSearch(start, 0, threshold, goal);
        if (result == -1) return threshold; // 목표 도달
        if (result == Integer.MAX_VALUE) return -1; // 경로 없음
        threshold = result; // 다음 임계값
    }
}