종합: 지도 요구에서 경로와 검사까지

무가중·가중 요구를 구분하고 함수의 정답을 독립적인 조건으로 검증합니다.

이제 자료 표현·알고리즘 선택·출력·검사를 하나의 문제로 연결합니다. 목표는 같은 지도에서도 '최소 이동 수'와 '최소 비용'이 다른 결과를 만든다는 사실을 실행으로 설명하는 것입니다. BFS·Dijkstra·경로 복원을 먼저 읽으세요.

개념과 약속

문제는 S에서 T로 이동하는 경로입니다. S→T는 비용 10인 한 간선, S→A와 A→T는 비용 2씩인 두 간선입니다. 요구가 최소 간선 수라면 직접 S→T, 요구가 최소 비용이면 S→A→T가 맞습니다. 코드보다 먼저 반환할 거리의 단위를 써야 합니다.

출력 경로가 맞는지 확인하는 독립 조건은 출발·도착, 각 연속 정점의 실제 간선 존재, 비용 합, 요구한 최적 거리와의 일치입니다. 여러 최적 경로가 있다면 특정 문자열 하나와만 비교하지 않고 이 조건을 검증합니다. 부모 사전은 알고리즘이 만든 유효한 기록이라는 전제에서 복원 함수에 전달합니다.

비용은 앞 Dijkstra 본문과 같은 약속을 사용합니다. 0 이상의 Python 정수 또는 유한한 float를 받되 bool은 거부합니다. 정수 비용은 정확히 더하고, float 누적 합이나 정수/float 혼합 변환이 범위를 넘으면 ValueError로 중단합니다. 이 오류는 도달 불가능한 정점의 inf·빈 경로와 다릅니다. 아래 종합 예제는 작은 정수 비용을 사용합니다.

손으로 상태 추적하기

요구	알고리즘	거리	경로
최소 이동 수	BFS	간선 1개	S,T
최소 비용	Dijkstra	비용 4	S,A,T

검사에서는 비용 4라는 숫자뿐 아니라 S→A:2와 A→T:2가 실제 자료에 있는지도 확인합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

zip(path, path[1:])는 경로의 연속 두 정점을 한 쌍씩 줍니다. all(...)은 모든 쌍이 조건을 만족하는지 검사하고, sum(...)은 그 비용 합을 계산합니다. 비용 사전의 (v,w) 키는 출발·도착 두 이름의 튜플입니다.

from collections import deque
import heapq
import math

def bfs_distances(graph, start):
    if start not in graph:
        raise ValueError("start must be a vertex")
    distance, parent = {start: 0}, {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return distance, parent


def dijkstra(graph, start):
    vertices = set(graph)
    for edges in graph.values():
        for target, weight in edges:
            if type(weight) not in (int, float) or weight < 0 or (type(weight) is float and not math.isfinite(weight)):
                raise ValueError("nonnegative int or finite float weights required")
            vertices.add(target)
    if start not in vertices:
        raise ValueError("start must be a vertex")
    distances = {vertex: math.inf for vertex in vertices}
    distances[start] = 0
    parent = {start: None}
    queue = [(0, start)]
    while queue:
        cost, vertex = heapq.heappop(queue)
        if cost != distances[vertex]:
            continue
        for target, weight in graph.get(vertex, []):
            try:
                candidate = cost + weight
            except OverflowError as error:
                raise ValueError("path cost exceeds float range") from error
            if type(candidate) is float and not math.isfinite(candidate):
                raise ValueError("path cost exceeds float range")
            if candidate < distances[target]:
                distances[target] = candidate
                parent[target] = vertex
                heapq.heappush(queue, (candidate, target))
    return distances, parent


def restore_path(parent, target):
    if target not in parent:
        return []
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


graph = {"S": [("T", 10), ("A", 2)], "A": [("T", 2)], "T": []}
unweighted = {v: [neighbor for neighbor, _ in edges] for v, edges in graph.items()}
steps, step_parent = bfs_distances(unweighted, "S")
costs, cost_parent = dijkstra(graph, "S")
path = restore_path(cost_parent, "T")
print(steps["T"], restore_path(step_parent, "T"))
print(costs["T"], path)
assert path[0] == "S" and path[-1] == "T"
edge_cost = {(v, w): cost for v, edges in graph.items() for w, cost in edges}
assert all((v, w) in edge_cost for v, w in zip(path, path[1:]))
assert sum(edge_cost[v, w] for v, w in zip(path, path[1:])) == costs["T"]
print("경로 조건 통과")

실행 결과:

1 ['S', 'T']
4 ['S', 'A', 'T']
경로 조건 통과

왜 맞고 언제 끝나는가

BFS의 거리 층은 간선 수를 최소화하고 Dijkstra의 비음수 완화는 비용 합을 최소화합니다. 서로 다른 명세를 각각 충족하므로 출력 차이는 오류가 아닙니다. 경로 조건 검사는 반환 데이터가 실제 입력과 일치하는지 확인하며 알고리즘의 최적성 증명과 함께 사용합니다.

비용과 적용 범위

BFS O(V+E), 이 힙 기반 Dijkstra O((V+E) log(V+E))를 비교합니다. 경로 조건 검사는 경로 길이에 비례하되, 별도의 간선 사전을 만들면 O(E) 준비 비용이 있습니다. 여기 간선 비용 사전은 동일 출발·도착의 다중 간선이 없다는 입력 약속을 사용합니다.