그래프 탐색 경로 계획 - BFS·다익스트라·A*

이 장에서 배우는 것

앞 장에서 만든 점유 격자 지도는 로봇이 들어갈 수 있는 곳과 피해야 할 곳을 구분한다. 그러나 빈 칸을 안다고 해서 목적지까지 이동하는 순서가 정해지지는 않는다. 이번에는 창고의 출발 위치와 배송 위치를 정점으로 연결하고, 그 사이에서 경로를 찾는다. 같은 지도라도 무엇을 비용으로 삼느냐에 따라 선택할 경로가 달라진다는 점이 핵심이다.

너비 우선 탐색(Breadth-First Search, BFS), 다익스트라 탐색(Dijkstra’s algorithm), A* 탐색(A-star search)을 같은 입력과 같은 비용 정의로 비교한다. 세 알고리즘의 차이를 자료 구조만으로 외우지 않고, 다음에 꺼낼 후보를 어떤 기준으로 고르는지 살펴본다. 실습은 지도 한 장에서 경로를 반환하는 데 집중한다.

• 점유 격자의 이동 가능한 칸과 인접 관계를 격자 그래프로 표현한다.
• 이동 횟수와 누적 이동 비용을 구분하고 탐색 결과를 비교한다.
• 휴리스틱이 A*의 탐색 순서와 최적성에 미치는 영향을 설명한다.
• 부모 정보를 따라 경로를 복원하고 도달 불가능한 목적지를 처리한다.
• 같은 비용의 후보가 생겨도 실행 결과가 일정하도록 구현한다.

문제 상황

창고 로봇이 왼쪽 집하 위치에서 오른쪽 포장 위치로 상자를 옮긴다고 하자. 두 위치를 곧바로 잇는 통로에는 작업자가 자주 머문다. 통행 자체가 금지되지는 않지만, 로봇은 속도를 낮추거나 기다려야 한다. 위쪽과 아래쪽에는 조금 돌아가는 일반 통로가 있다. 칸 수만 세면 가운데 통로가 짧지만, 운영자가 원하는 것은 기다림을 포함한 부담이 작은 경로다.

이 장에서는 일반 칸에 들어가는 비용을 1, 가운데 혼잡 칸에 들어가는 비용을 5로 정한다. 비용은 초 단위의 정밀한 예측값이 아니라 통로를 비교하기 위한 양의 정수다. 실제 이동 시간으로 해석하려면 각 값이 같은 단위와 같은 기준으로 산정되어야 한다. 여기서는 비용 정의에 따른 경로 선택만 확인한다.

실습 지도는 바깥쪽이 벽으로 둘러싸인 세 줄짜리 통로다. 출발점과 목표점 사이에는 혼잡 칸이 다섯 개 있다. 직진하면 여섯 번 이동하며, 위쪽으로 우회하면 여덟 번 이동한다. 지도는 탐색 중 변하지 않는다고 가정한다. 로봇이 이동하는 동안 사람이 들어오는 상황과 주행 명령 생성은 이 프로그램의 범위에 넣지 않는다.

격자를 그래프로 바꾸기

정점과 간선의 의미

그래프(graph)는 정점과 정점 사이의 연결로 이루어진다. 이 실습에서는 벽이 아닌 칸 하나가 정점 하나다. 두 칸이 위아래 또는 좌우로 붙어 있고 모두 이동 가능하면 그 사이에 간선이 있다. 대각선 이동은 허용하지 않는다. 따라서 한 번 이동할 때 행 또는 열 중 하나만 1만큼 바뀐다.

좌표는 일관되게 (행, 열) 순서로 기록한다. 배열의 첫 인덱스가 행이고 둘째 인덱스가 열이므로, 지도 접근도 grid[row, col]이다. 화면에서 오른쪽으로 이동하면 열이 증가하고 아래쪽으로 이동하면 행이 증가한다. 기본서에서 사용한 물리 좌표와 연결하려면 별도의 변환이 필요하지만, 이번 탐색은 격자 좌표 안에서 끝난다.

벽은 높은 비용을 가진 정점으로 처리하지 않는다. 아예 이웃 후보에서 제외한다. 높은 비용은 필요하다면 지나갈 수 있다는 뜻이고, 벽은 지나갈 수 없다는 뜻이기 때문이다. 입력 지도의 미확인 칸을 허용할지도 탐색 전에 결정해야 한다. 실습 지도에는 미확인 칸이 없으며, 모든 통로가 알려져 있다.

여기서 이동 가능하다는 판단은 로봇 중심이 해당 칸에 있어도 충돌하지 않는다는 전제를 포함한다. 실제 창고에서는 로봇의 폭과 여유 간격을 고려해 통로를 정리한 지도를 입력해야 한다. 탐색기가 빈 칸 사이의 연결을 찾았다는 사실만으로 로봇 몸체의 통과 가능성까지 확인되는 것은 아니다.

비용을 어느 이동에 붙일 것인가

현재 칸을 u, 다음 칸을 v라고 할 때 이동 비용을 c(u, v) = cost[v]로 정의한다. 출발 칸의 비용은 더하지 않고, 첫 이동부터 목표 칸에 들어갈 때까지의 비용을 합한다. 경로에 정점이 일곱 개 있으면 이동은 여섯 번이다. 이 둘을 혼동하면 출발점 비용을 중복해서 더하거나 이동 횟수를 하나 크게 계산하게 된다.

두 방향 모두 이동할 수 있어도 비용은 방향에 따라 다를 수 있다. 일반 칸에서 혼잡 칸으로 들어가는 비용은 5지만, 같은 간선을 반대로 지나 일반 칸으로 들어가는 비용은 1이다. 연결 관계는 대칭이어도 가중치는 대칭일 필요가 없다. 다익스트라와 A*는 이와 같은 방향별 비용도 다룬다.

실습 지도의 기호와 진입 비용

기호	뜻	진입 비용	이웃 후보
#	벽	사용하지 않음	제외
.	일반 통로	1	포함
5	혼잡 통로	5	포함
S, G	출발점, 목표점	1	포함

실습의 이동 가능한 정점은 21개다. 각 정점은 많아야 네 개의 이웃만 가지므로, 연결 관계 전체를 큰 행렬에 저장할 필요가 없다. 현재 칸을 꺼낼 때 네 방향을 검사하면 충분하다. 지도 배열과 이웃 생성 함수만으로 격자 그래프를 암묵적으로 표현할 수 있다.

BFS와 다익스트라가 고르는 다음 칸

BFS는 이동 횟수 순서로 넓어진다

BFS는 먼저 넣은 후보를 먼저 꺼내는 큐(queue)를 사용한다. 출발점에서 한 번 이동해 도착하는 칸들이 두 번 이동해야 하는 칸들보다 먼저 처리된다. 모든 간선의 비용이 같을 때는 이동 횟수가 적은 경로가 비용도 작으므로, BFS만으로 최소 비용 경로를 구할 수 있다.

이 성질은 서로 다른 진입 비용까지 비교해 주지는 않는다. 실습에서 BFS는 가운데 통로를 곧바로 지난다. 이동 횟수는 6으로 최소지만 비용은 5 × 5 + 1 = 26이다. 알고리즘이 잘못된 경로를 만든 것이 아니라, BFS의 최적화 기준과 창고 운영의 비용 기준이 다르다.

BFS에서는 후보를 큐에 넣을 때 발견 여부를 기록한다. 같은 칸을 나중에 다시 발견해도 이동 횟수가 더 작아지지 않으므로 중복 등록할 필요가 없다. 부모 사전은 발견 여부를 나타내면서, 그 칸에 도달하기 직전에 있던 칸도 함께 보관한다.

다익스트라는 지금까지 든 비용을 비교한다

다익스트라는 출발점에서 현재 칸까지 알려진 최소 비용을 g로 저장한다. 다음 후보는 이동 횟수가 아니라 g가 가장 작은 항목이다. 이를 위해 우선순위 큐(priority queue)를 최소 힙으로 구현한다. 비용이 모두 음수가 아닐 때, 유효한 최소 비용 항목을 꺼낸 정점의 거리는 확정할 수 있다.

새 경로의 비용이 기존 값보다 작으면 거리와 부모를 갱신한다. 이 작업을 완화(relaxation)라고 한다. 처음 발견한 경로가 최선이라는 보장이 없으므로 BFS처럼 발견 여부만으로 이후의 후보를 차단해서는 안 된다. 처음에는 혼잡 통로 쪽에서 도달한 칸이 나중에는 일반 통로를 돌아가는 경로로 더 싸게 연결될 수도 있다.

파이썬의 힙에서 기존 항목의 우선순위를 직접 바꾸는 대신, 개선된 항목을 새로 넣는다. 그러면 예전 비용을 가진 항목이 힙 안에 남는다. 꺼낸 항목의 비용이 현재 거리 사전의 값과 다르면 오래된 정보이므로 버린다. 이번 코드는 이 방식을 A*와 공유한다.

목표를 이웃으로 발견한 순간에는 탐색을 종료하지 않는다. 목표에 들어가는 더 싼 경로가 아직 후보로 남아 있을 수 있기 때문이다. 오래된 항목을 걸러낸 뒤 목표가 최소 우선순위 항목으로 꺼내졌을 때 경로를 반환한다.

A*의 휴리스틱과 비용 비교

A*는 이미 사용한 비용 g에 목표까지 남은 비용의 추정값 h를 더한다. 이 추정 함수를 휴리스틱(heuristic)이라고 부른다. 후보의 우선순위는 f = g + h다. 출발점에서 얼마나 싸게 왔는지뿐 아니라 목표까지 얼마나 더 가야 할지도 함께 고려한다.

네 방향 이동에서는 맨해튼 거리(Manhattan distance)를 사용할 수 있다. 현재 칸이 (r, c), 목표가 (rg, cg)이면 거리값은 abs(r - rg) + abs(c - cg)다. 모든 이동 비용의 하한을 m이라고 할 때 h를 이 거리의 m배로 정한다. 실습의 최소 진입 비용은 1이므로 거리값 자체가 비용의 하한이다.

이 추정은 벽과 혼잡 구간을 무시한다. 실제 이동에서는 장애물을 돌아가거나 비싼 칸을 지날 수 있으므로 실제 최소 비용이 더 커질 수 있다. 실습의 출발점에서 목표까지 맨해튼 거리는 6이지만, 최소 비용은 8이다. 남은 비용을 정확히 맞히지 않아도 유용하며, 최적성을 유지하려면 실제 최소 비용을 넘겨 짐작하지 않는 성질이 중요하다.

일관성도 확인할 수 있다. 이웃 u와 v에 대해 h(u) ≤ c(u, v) + h(v)가 성립하면 휴리스틱이 일관적이다. 한 번 이동하면 맨해튼 거리는 최대 1만 줄고, 이동 비용은 최소 1이므로 이번 h는 이 조건을 만족한다. 목표의 h는 0이며, 이 조건 아래에서 목표의 유효 항목을 꺼냈을 때 최소 비용 경로를 반환할 수 있다.

A*에서 h를 0으로 두면 우선순위가 g만 남으므로 다익스트라가 된다. 반대로 맨해튼 거리를 임의로 크게 늘리면 목표 쪽 후보를 더 강하게 선호하지만, 최소 비용 경로를 보장하는 근거가 사라질 수 있다. 특히 이동 비용이 1보다 작은 지도에서는 거리값을 그대로 사용하지 말고 올바른 비용 하한을 곱해야 한다.

세 탐색이 사용하는 우선순위와 보장 조건

탐색	다음 후보 기준	최소화하는 값	주요 조건
BFS	큐에 들어온 순서	이동 횟수	비용 최적성은 동일 간선 비용일 때
다익스트라	g	누적 비용	음수 간선 비용 없음
A*	g + h	누적 비용	이 구현에서는 일관적인 h 사용

같은 우선순위를 가진 후보의 처리 순서도 정한다. 이웃은 위, 오른쪽, 아래, 왼쪽 순서로 생성하고, 힙에는 증가하는 일련번호를 함께 넣는다. 우선순위가 같으면 먼저 들어간 후보가 먼저 나온다. 이 규칙은 최소 비용 자체를 바꾸지 않지만, 같은 비용의 경로가 여러 개일 때 어느 경로를 출력하는지 결정한다.

A*가 모든 지도에서 다익스트라보다 적은 계산으로 끝나는 것은 아니다. 휴리스틱이 실제 남은 비용을 거의 구분하지 못하거나 같은 f를 가진 후보가 많으면 탐색 범위가 비슷해질 수 있다. 이번 비교표는 경로의 비용을 비교하며 실행 시간의 우열을 주장하지 않는다.

완성 코드

다음 내용을 graph_search.py로 저장한다. 파이썬 표준 라이브러리와 NumPy만 사용한다. 무작위 값을 생성하지 않으므로 시드와 관계없이 같은 결과를 낸다. 정수 비용, 고정된 이웃 순서, 힙의 일련번호를 함께 사용해 같은 비용의 후보 순서도 일정하게 만든다.

from collections import deque
from heapq import heappop, heappush
from itertools import count

import numpy as np


MAP = (
    "#########",
    "#.......#",
    "#S55555G#",
    "#.......#",
    "#########",
)
DIRECTIONS = ((-1, 0), (0, 1), (1, 0), (0, -1))


def make_world():
    grid = np.array([list(row) for row in MAP])
    costs = np.ones(grid.shape, dtype=np.int64)
    costs[grid == "5"] = 5
    start = tuple(int(x) for x in np.argwhere(grid == "S")[0])
    goal = tuple(int(x) for x in np.argwhere(grid == "G")[0])
    return grid, costs, start, goal


def neighbors(grid, node):
    rows, cols = grid.shape
    row, col = node
    for dr, dc in DIRECTIONS:
        nr, nc = row + dr, col + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            if grid[nr, nc] != "#":
                yield (nr, nc)


def reconstruct(parent, goal):
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path


def bfs(grid, start, goal):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        node = frontier.popleft()
        if node == goal:
            return reconstruct(parent, goal)
        for nxt in neighbors(grid, node):
            if nxt not in parent:
                parent[nxt] = node
                frontier.append(nxt)
    return None


def manhattan(node, goal):
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])


def best_first(grid, costs, start, goal, heuristic):
    serial = count()
    distance = {start: 0}
    parent = {start: None}
    frontier = []
    heappush(frontier, (heuristic(start, goal), next(serial), 0, start))

    while frontier:
        _, _, saved_g, node = heappop(frontier)
        if saved_g != distance[node]:
            continue
        if node == goal:
            return reconstruct(parent, goal)

        for nxt in neighbors(grid, node):
            candidate = saved_g + int(costs[nxt])
            if candidate < distance.get(nxt, float("inf")):
                distance[nxt] = candidate
                parent[nxt] = node
                priority = candidate + heuristic(nxt, goal)
                heappush(
                    frontier,
                    (priority, next(serial), candidate, nxt),
                )
    return None


def path_cost(costs, path):
    return sum(int(costs[node]) for node in path[1:])


def validate_path(grid, start, goal, path):
    if not path or path[0] != start or path[-1] != goal:
        raise ValueError("経路の端点が不正です")
    for current, nxt in zip(path, path[1:]):
        if nxt not in neighbors(grid, current):
            raise ValueError("経路に不正な移動があります")


def main():
    grid, costs, start, goal = make_world()
    if np.any(costs[grid != "#"] < 1):
        raise ValueError("이 실습의 이동 비용은 1 이상이어야 한다")

    results = (
        ("BFS", bfs(grid, start, goal)),
        (
            "다익스트라",
            best_first(grid, costs, start, goal, lambda node, target: 0),
        ),
        ("A*", best_first(grid, costs, start, goal, manhattan)),
    )

    print("지도")
    for row in MAP:
        print(row)
    for name, path in results:
        if path is None:
            print(f"{name}: 경로 없음")
            continue
        validate_path(grid, start, goal, path)
        steps = len(path) - 1
        total = path_cost(costs, path)
        print(f"{name}: 이동={steps}, 비용={total}")
        print("경로: " + " -> ".join(str(node) for node in path))


if __name__ == "__main__":
    main()

줄별 해설

지도 생성과 이웃 검사

deque는 BFS의 양끝 큐를 제공하며, 여기서는 오른쪽에 넣고 왼쪽에서 꺼낸다. heappop과 heappush는 최소 힙을 다루고, count는 동률 후보를 구분하는 정수를 차례로 만든다. 지도 계산에 필요한 외부 패키지는 NumPy 하나다.

MAP은 사람이 확인하기 쉬운 문자열 튜플이다. make_world의 첫 줄은 이를 문자 배열로 바꾼다. 다음 두 줄은 같은 크기의 비용 배열을 만들고 혼잡 칸만 5로 바꾼다. 벽 위치에도 배열 값은 있지만 이웃 검사에서 제외되므로 탐색 비용으로 사용되지 않는다.

np.argwhere는 조건에 맞는 좌표를 찾는다. 이 고정 지도에는 S와 G가 각각 하나씩 있다. 좌표 성분을 int로 바꾸는 이유는 사전의 키와 출력에 일반 파이썬 정수를 사용하기 위해서다. 외부 지도를 읽는 프로그램으로 확장한다면 S와 G의 개수도 검사해야 한다.

neighbors는 네 방향마다 후보 좌표를 계산한다. 먼저 배열 범위를 확인하고 그 안에서 벽 여부를 검사한다. 이 순서는 음수 인덱스가 배열의 반대쪽을 가리키는 문제를 막는다. yield를 사용하므로 호출자는 유효한 이웃을 하나씩 받아 순회한다.

발견 기록과 경로 복원

reconstruct는 목표에서 시작해 부모를 거슬러 올라간다. 출발점의 부모는 None이므로 그 지점에서 반복이 끝난다. 이때 목록은 목표부터 출발점 순서이므로 마지막에 뒤집는다. 전체 경로를 후보마다 복사하지 않고 부모 하나만 저장해도 경로를 되살릴 수 있다.

bfs에서 출발점은 처음부터 큐와 부모 사전에 들어 있다. popleft로 후보를 꺼내고, 아직 부모 사전에 없는 이웃만 등록한다. 부모 등록과 큐 삽입이 붙어 있으므로 다른 후보가 같은 이웃을 발견하더라도 중복 삽입하지 않는다. 큐가 빌 때까지 목표를 찾지 못하면 None을 반환한다.

출발점과 목표점이 같아도 두 탐색 함수는 첫 후보를 꺼낸 직후 길이가 1인 경로를 반환한다. 이동 횟수는 0이며 path[1:]가 비어 있으므로 비용도 0이다. 반면 경로를 찾지 못한 경우는 빈 경로와 섞지 않고 None으로 구분한다.

힙 항목의 네 값

best_first는 휴리스틱 함수를 인수로 받는다. 힙 항목은 (우선순위, 일련번호, 저장한 g, 좌표) 순서다. 튜플은 앞쪽 값부터 비교되므로 먼저 우선순위가 적용되고, 동률이면 일련번호가 순서를 결정한다. 저장한 g는 오래된 항목인지 판단하기 위한 값이다.

saved_g != distance[node] 검사는 갱신 전의 항목을 건너뛴다. 이번에는 정수 비용을 사용하므로 같은 누적 비용을 정확히 비교할 수 있다. 실수 비용으로 확장할 때는 반올림 방식과 비교 정책을 함께 검토해야 한다. 다만 작은 차이를 무조건 같은 값으로 취급하면 실제 개선까지 지울 수 있다.

candidate에는 현재 비용과 다음 칸의 진입 비용을 더한다. 그 결과가 기존 값보다 작을 때만 거리와 부모를 바꾼다. 같은 비용은 갱신하지 않으므로 먼저 발견한 동률 경로가 유지된다. 함수는 영구적으로 닫힌 정점 집합을 두지 않아, 이미 꺼낸 칸이라도 더 작은 g가 발견되면 다시 후보에 넣을 수 있다.

main에서 다익스트라에는 항상 0을 반환하는 함수를, A*에는 manhattan을 전달한다. 두 알고리즘이 같은 비용 합산과 같은 부모 갱신 코드를 사용하므로 비교 기준이 어긋나지 않는다. BFS가 비용 배열을 인수로 받지 않는 것은 비용 크기를 탐색 순서에 사용하지 않기 때문이다.

validate_path는 양 끝점과 각 이동의 연결을 검사한다. 경로가 지도 규칙을 지키는지는 확인하지만 최소 비용까지 증명하지는 않는다. path_cost는 출발점을 제외하고 비용을 더하며, 출력부는 탐색 결과의 이동 횟수와 비용을 별도로 보여 준다.

실행 결과

NumPy가 설치된 환경에서 다음 명령을 실행한다. 첫 명령은 경고를 오류로 취급하면서 문법을 컴파일한다. 정상적으로 끝나면 별도 출력이 없다. 둘째 명령이 프로그램을 실행한다.

python3 -W error -m py_compile graph_search.py
python3 -W error graph_search.py

예상 출력은 다음과 같다. 좌표는 0부터 시작하는 행과 열이다. 우회 경로는 위쪽과 아래쪽의 비용이 같지만, 이웃 순서와 일련번호 규칙에 따라 위쪽 경로가 출력된다.

지도
#########
#.......#
#S55555G#
#.......#
#########
BFS: 이동=6, 비용=26
경로: (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (2, 5) -> (2, 6) -> (2, 7)
다익스트라: 이동=8, 비용=8
경로: (2, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) -> (1, 5) -> (1, 6) -> (1, 7) -> (2, 7)
A*: 이동=8, 비용=8
경로: (2, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (1, 4) -> (1, 5) -> (1, 6) -> (1, 7) -> (2, 7)

같은 지도에서 얻은 이동 횟수와 누적 비용

탐색	이동 횟수	누적 비용	선택한 통로
BFS	6	26	가운데 직진
다익스트라	8	8	위쪽 우회
A*	8	8	위쪽 우회

우회 경로의 비용 8이 최소라는 사실도 지도에서 확인할 수 있다. 행을 바꾸지 않는 경로는 가운데 통로를 지나므로 비용이 26이다. 가운데 행을 벗어났다가 목표 행으로 돌아오려면 최소 두 번의 세로 이동과 여섯 번의 가로 이동이 필요하다. 모든 이동 비용이 1 이상이므로 그런 경로의 비용은 최소 8이며, 출력된 경로가 그 값을 달성한다.

표의 비용 차이는 BFS가 느리거나 부정확해서 생긴 결과가 아니다. BFS는 최소 이동 횟수라는 자신의 기준을 충족한다. 경로 계획에서는 알고리즘을 고르기 전에 비용이 운영 목적을 표현하는지 확인해야 한다. 혼잡 비용이 잘못되면 최소 비용 탐색도 잘못된 운영 판단을 충실하게 따르게 된다.

실무에서 자주 틀리는 것

배열 접근 뒤에 범위를 검사한다

다음 코드는 오른쪽이나 아래쪽 경계를 넘으면 예외가 나고, 음수 인덱스에서는 반대편 칸을 읽을 수도 있다. 벽으로 둘러싼 실습 지도에서 문제가 드러나지 않았다고 해서 이웃 함수가 일반적으로 안전한 것은 아니다.

# 틀린 코드
if grid[nr, nc] != "#":
    yield (nr, nc)

# 고친 코드
if 0 <= nr < rows and 0 <= nc < cols:
    if grid[nr, nc] != "#":
        yield (nr, nc)

가중치 탐색에서 첫 발견을 확정으로 취급한다

다익스트라와 A*에서 발견된 칸이라는 이유만으로 갱신을 막으면 더 싼 우회 경로를 놓친다. 존재 여부 대신 새 누적 비용이 기존 값보다 작은지 비교해야 한다. 아래의 갱신 뒤에는 완성 코드처럼 새 항목을 힙에 넣는다.

# 틀린 코드
if nxt not in distance:
    distance[nxt] = candidate
    parent[nxt] = node

# 고친 코드
if candidate < distance.get(nxt, float("inf")):
    distance[nxt] = candidate
    parent[nxt] = node

목표를 발견하자마자 반환한다

가중치 탐색에서 목표가 이웃에 나타났다는 사실은 최적 비용의 확정을 뜻하지 않는다. 잘못된 위치에서 반환하면 부모 사전을 갱신하기 전이라 복원에 실패할 수도 있다. 종료 조건은 힙에서 유효한 항목을 꺼낸 직후에 둔다.

# 틀린 코드: 이웃을 순회하는 중에 종료한다.
if nxt == goal:
    return reconstruct(parent, goal)

# 고친 코드: 힙에서 꺼낸 직후에 검사한다.
_, _, saved_g, node = heappop(frontier)
if saved_g != distance[node]:
    continue
if node == goal:
    return reconstruct(parent, goal)

휴리스틱을 임의의 배수로 키운다

목표를 향해 더 빠르게 탐색하고 싶다는 이유로 거리를 크게 곱하면 하한 성질을 잃을 수 있다. 현재 지도에서 출발점의 거리 6에 3을 곱한 18은 실제 최소 비용 8보다 크다. 아래 수정은 모든 이동이 한 칸이고 최소 진입 비용이 양수인 조건에서 적용한다.

# 틀린 코드: 최소 비용 보장을 유지하려는 경우
def heuristic(node, goal):
    return 3 * manhattan(node, goal)

# 고친 코드
min_cost = int(costs[grid != "#"].min())

def heuristic(node, goal):
    return min_cost * manhattan(node, goal)

대각선 이동을 추가하면 이 수정만으로 충분하지 않을 수 있다. 이동 한 번이 행과 열을 동시에 바꿀 수 있으므로 맨해튼 거리의 하한 근거를 다시 검토해야 한다. 이웃 정의, 이동 비용, 휴리스틱은 한 묶음으로 설계한다.

한눈에 보기

격자 경로 탐색을 구현할 때 확인할 기준

항목	이번 장의 선택	확인할 이유
상태	행과 열의 튜플	배열 접근과 좌표 해석을 일치시킨다
연결	네 방향의 이동 가능한 칸	실제로 허용한 이동만 탐색한다
비용	도착 칸의 진입 비용	탐색과 결과 평가의 기준을 맞춘다
BFS	발견 시 부모 등록	중복 후보 없이 최소 이동 횟수를 찾는다
가중치 탐색	더 작은 g이면 갱신	늦게 발견한 저비용 경로를 반영한다
A*의 h	맨해튼 거리	이번 비용 체계에서 남은 비용의 하한이다
경로 없음	None 반환	정지 상태와 탐색 실패를 구분한다
동률 처리	이웃 순서와 일련번호 고정	반복 실행에서 같은 경로를 얻는다

정점 수를 V, 간선 수를 E라고 하면 BFS는 시간과 저장 공간을 지도 규모에 비례해 사용한다. 구체적으로 시간은 O(V + E)이며, 네 방향 격자에서는 E가 V에 비례한다. 이번처럼 중복 힙 항목을 허용하는 다익스트라는 연결된 격자에서 O(V log V)의 시간 범위로 정리할 수 있다. 일관적인 휴리스틱을 쓰는 A*도 이론적 최악의 차수만으로 큰 차이를 기대하기는 어렵다. 실제 차이는 목표에 도달하기까지 얼마나 많은 정점을 처리하는지에서 나타난다.

격자 탐색은 이동 가능한 상태와 연결을 미리 규칙적으로 정할 수 있을 때 이해하고 검증하기 쉽다. 반면 공간을 아주 잘게 나누면 정점 수가 빠르게 늘어난다. 다음 장에서 다룰 샘플링 기반 계획은 공간의 모든 칸을 같은 밀도로 준비하는 방식과 다른 출발점을 가진다.

연습 문제

1. 가운데 혼잡 칸의 진입 비용을 모두 1로 바꾼다. 세 탐색의 이동 횟수와 비용을 예상한 뒤 확인한다. 지도에 표시된 기호와 실제 비용 배열 중 무엇이 탐색 결과를 결정하는지도 설명한다.
2. 시작 칸 (2, 1)의 위쪽, 오른쪽, 아래쪽 칸을 벽으로 바꾼다. 왼쪽은 기존 벽이다. 세 함수가 무엇을 반환해야 하는지 설명하고, 출력부가 이 결과를 어떻게 처리하는지 확인한다.
3. A*의 휴리스틱을 항상 0으로 바꾼다. 최소 비용뿐 아니라 이번 구현에서 탐색 순서도 다익스트라와 같아지는 이유를 설명한다.
4. 일반 칸의 비용은 1로 유지하고, 가운데 혼잡 칸 다섯 개의 비용을 양의 실수 k로 통일한다. 직진과 우회의 비용이 같아지는 k를 구한다. k가 1보다 작을 때 맨해튼 거리를 그대로 휴리스틱으로 사용해도 되는지 설명한다.

정답과 해설

1. 세 탐색 모두 이동 횟수 6, 비용 6인 가운데 직진 경로를 얻는다. costs[grid == "5"] = 5를 costs[grid == "5"] = 1로 바꾸면 된다. 지도에 5라는 기호가 남아 있어도 가중치 탐색에 사용되는 값은 비용 배열의 값이다. 다만 사람이 결과를 읽을 때 혼동하지 않도록 실제 프로그램에서는 표시도 비용과 맞추는 편이 좋다. 모든 간선 비용이 같아졌으므로 최소 이동 횟수와 최소 비용이 같은 기준이 된다.

2. grid[1, 1], grid[2, 2], grid[3, 1]을 벽으로 바꾸면 시작점에서 나갈 수 없다. 세 탐색은 시작점을 처리한 뒤 후보가 없어져 None을 반환한다. 출력부는 각 탐색에 대해 경로 없음을 출력하고 경로 비용 계산을 건너뛴다. 완성 코드의 지도 출력은 원본 MAP을 사용하므로 배열만 수정했다면 출력도 배열을 순회하도록 바꿔야 변경한 벽이 보인다.

3. 두 실행의 우선순위가 모두 g가 된다. 같은 함수를 사용하고 이웃 순서, 갱신 조건, 일련번호 생성 방식도 같으므로 후보 삽입과 꺼내기 순서가 일치한다. 우회 경로의 비용은 여전히 8이다. 이 결과는 A*가 g와 별개의 비용을 최소화하는 것이 아니라, 같은 비용 문제에 남은 거리의 정보를 추가한다는 점을 보여 준다.

4. 직진 비용은 5k + 1이고 우회 비용은 8이다. 따라서 k = 7 / 5 = 1.4에서 비용이 같다. 그보다 작으면 직진이, 크면 우회가 더 싸다. k가 1보다 작으면 한 칸 이동 비용이 1보다 작을 수 있어 맨해튼 거리가 실제 비용을 넘길 수 있다. 이 경우 min(1, k)를 곱하면 유효한 하한을 만들 수 있다. 실수 비용을 실제 코드에 넣으려면 비용 배열을 실수 자료형으로 바꾸고, int 변환과 1 이상 검사도 수정해야 한다. 이 문제는 정수 전제의 코드를 그대로 실행하는 문제가 아니라 비용 모델의 경계를 분석하는 문제다.