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

마지막 장에서는 지금까지 배운 것을 하나의 문제에 함께 적용합니다. 동네 지도에서 집 S에서 목적지 T까지 가는 길을 찾아 주는 프로그램을 만든다고 해 봅시다. 막상 코드를 짜려고 하면 "가장 좋은 길"이 무엇인지부터 정해야 한다는 것을 알게 됩니다. 갈아타는 횟수가 가장 적은 길일 수도 있고, 걸리는 시간이 가장 짧은 길일 수도 있습니다. 이 글에서는 요구를 먼저 정하고, 요구에 맞는 알고리즘을 고르고, 그 결과가 정말 맞는지를 알고리즘과 상관없는 방법으로 검사하는 과정을 처음부터 끝까지 따라갑니다.

요구를 먼저 정한다

아래 지도의 간선은 한 방향으로만 갈 수 있는 길이고, 숫자는 걸리는 시간(분)입니다.

S에서 T로 바로 가는 길은 간선 하나짜리지만 12분이 걸립니다. S→B→A→T는 간선 세 개를 지나지만 1 + 2 + 1 = 4분이면 됩니다. "가장 적은 길을 거쳐서"라는 요구라면 S→T가 답이고, "가장 빨리"라는 요구라면 S→B→A→T가 답입니다. 두 답은 서로 다른 질문에 대한 맞는 답이므로, 어느 쪽이 틀린 것이 아닙니다. 프로그램을 짜기 전에 반환할 값의 단위, 곧 간선의 개수인지 시간의 합인지를 먼저 적어 두어야 하는 이유입니다.

요구가 정해지면 알고리즘도 정해집니다. 간선의 개수를 줄이는 문제는 BFS가, 음수가 아닌 비용의 합을 줄이는 문제는 Dijkstra 알고리즘이 풉니다. 같은 인접 목록에서 BFS는 비용을 무시하고 이웃만 보고, Dijkstra 알고리즘은 비용까지 봅니다. U는 T로 가는 길만 있고 S에서 U로 가는 길은 없는 장소로, 닿을 수 없는 경우를 보려고 넣었습니다.

결과를 어떻게 확인할까

두 알고리즘이 돌려준 경로가 맞는지 확인하는 방법은 두 단계로 나눌 수 있습니다. 첫째, 경로가 실제로 존재하는 길인지 확인합니다. 경로가 S에서 시작해 T에서 끝나고, 이어진 두 정점마다 그 간선이 지도에 있으며, 간선 비용의 합이 알고리즘이 알려 준 거리와 같아야 합니다. 이 조건은 정렬의 정답 조건에서 순서와 값의 개수를 확인한 것처럼, 알고리즘이 어떻게 동작했는지와 상관없이 결과만 보고 판단할 수 있습니다.

둘째, 그 경로가 정말 가장 좋은 경로인지 확인합니다. 첫째 조건은 존재하는 아무 길에서나 성립하므로, 이것만으로는 가장 좋다고 말할 수 없습니다. 작은 지도에서는 S에서 T로 가는, 같은 정점을 두 번 지나지 않는 모든 길을 나열해 그중 가장 좋은 것과 비교할 수 있습니다. 비용이 음수가 아니면 같은 정점을 두 번 지나는 길은 사이클을 빼서 비용을 줄이거나 그대로 둘 수 있으므로, 같은 정점을 두 번 지나지 않는 길만 보아도 충분합니다. 이 방법은 길의 수가 폭발적으로 늘어나 큰 지도에는 쓸 수 없지만, 작은 지도에서 빠른 알고리즘의 결과를 확인하는 기준 구현으로는 아주 좋습니다.

코드로 확인하기

아래 코드는 앞에서 만든 BFS, Dijkstra 알고리즘, 경로 복원을 다시 정의하고, 경로의 비용을 계산하는 path_cost와 모든 단순 경로를 나열하는 simple_paths를 더합니다. BFS는 비용이 붙은 인접 목록에서 이웃만 꺼내 쓰도록 조금 고쳤습니다.

from collections import deque
import heapq
import math


def bfs(graph, start):
    distance, parent = {start: 0}, {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor, _ in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return distance, parent


def dijkstra(graph, start):
    for edges in graph.values():
        for _, weight in edges:
            if weight < 0:
                raise ValueError("음수 비용의 간선은 다룰 수 없습니다")
    distance = {vertex: math.inf for vertex in graph}
    distance[start] = 0
    parent = {start: None}
    queue = [(0, start)]
    while queue:
        cost, vertex = heapq.heappop(queue)
        if cost != distance[vertex]:
            continue
        for target, weight in graph[vertex]:
            candidate = cost + weight
            if candidate < distance[target]:
                distance[target] = candidate
                parent[target] = vertex
                heapq.heappush(queue, (candidate, target))
    return distance, 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]


def path_cost(graph, path):
    edge_cost = {(v, w): c for v, edges in graph.items() for w, c in edges}
    if not all((v, w) in edge_cost for v, w in zip(path, path[1:])):
        return None
    return sum(edge_cost[v, w] for v, w in zip(path, path[1:]))


def simple_paths(graph, start, goal, path=None):
    path = path or [start]
    if path[-1] == goal:
        yield list(path)
        return
    for neighbor, _ in graph[path[-1]]:
        if neighbor not in path:
            path.append(neighbor)
            yield from simple_paths(graph, start, goal, path)
            path.pop()


graph = {
    "S": [("A", 4), ("B", 1), ("T", 12)],
    "A": [("T", 1)],
    "B": [("A", 2), ("C", 5)],
    "C": [("T", 3)],
    "T": [],
    "U": [("T", 1)],
}
steps, step_parent = bfs(graph, "S")
costs, cost_parent = dijkstra(graph, "S")
fewest = restore_path(step_parent, "T")
cheapest = restore_path(cost_parent, "T")
print("가장 적은 간선", steps["T"], fewest, path_cost(graph, fewest))
print("가장 적은 시간", costs["T"], cheapest, path_cost(graph, cheapest))
print("닿을 수 없는 U", costs["U"], restore_path(cost_parent, "U"))
paths = list(simple_paths(graph, "S", "T"))
print(paths)
print(min(len(p) - 1 for p in paths), min(path_cost(graph, p) for p in paths))

가장 적은 간선 1 ['S', 'T'] 12
가장 적은 시간 4 ['S', 'B', 'A', 'T'] 4
닿을 수 없는 U inf []
[['S', 'A', 'T'], ['S', 'B', 'A', 'T'], ['S', 'B', 'C', 'T'], ['S', 'T']]
1 4

path_cost는 먼저 (출발, 도착) 튜플을 키로, 비용을 값으로 하는 딕셔너리를 만듭니다. zip(path, path[1:])은 경로에서 이어진 두 정점을 한 쌍씩 주므로, 모든 쌍이 딕셔너리에 있으면 실제로 있는 길이고 그 비용을 더해 돌려줍니다. 지도에 없는 간선이 하나라도 있으면 None을 돌려줍니다. 두 알고리즘이 돌려준 경로는 모두 실제로 있는 길이고, BFS 경로의 비용 12와 Dijkstra 경로의 비용 4도 각각 계산했습니다.

simple_paths는 재귀로 쓴 DFS를 조금 바꾼 생성기입니다. 지금까지의 길 path의 마지막 정점에서, 길에 아직 없는 이웃으로 한 칸씩 나아가 보고, 목표에 닿으면 그 길을 내놓습니다. yield from은 재귀 호출이 내놓는 길들을 그대로 이어서 내놓는 문법이고, path.pop()은 한 이웃을 다 살펴본 뒤 그 이웃을 길에서 빼 다음 이웃을 시도할 수 있게 합니다. 이렇게 가능한 선택을 하나씩 해 보고 되돌리며 모든 경우를 살피는 방법을 백트래킹(backtracking)이라고 합니다. 나열한 네 길 가운데 간선이 가장 적은 길은 간선 1개, 비용이 가장 적은 길은 4분으로, 두 알고리즘의 답과 같습니다.

한 지도에서 맞았다고 끝내지 말고, 무작위로 만든 작은 지도에서 여러 번 비교해 보는 것이 좋습니다. 정점이 2개에서 6개이고 간선과 0부터 9까지의 비용이 무작위인 지도 200개를 만들어, 처음 정점에서 마지막 정점까지 두 알고리즘의 결과와 모든 단순 경로의 최솟값을 비교하면 모두 같습니다. 길이 하나도 없는 지도에서는 두 알고리즘이 모두 닿을 수 없다고 알려 줍니다.

닿을 수 없을 때의 약속

U는 S에서 가는 길이 없으므로 거리가 무한대 inf이고 경로는 빈 리스트입니다. 이 결과를 받는 쪽은 경로를 쓰기 전에 빈 리스트인지 먼저 확인해야 합니다. 확인 없이 path[0]이나 path[-1]을 읽으면 IndexError가 나고, 무한대를 다른 거리와 더하거나 화면에 그대로 보여 주면 이상한 결과가 나옵니다. "닿을 수 없음"은 오류가 아니라 정상적인 답의 하나이므로, 예를 들어 화면에는 "갈 수 있는 길이 없습니다"라고 따로 알려 주는 식으로 처리를 정해 두는 것이 좋습니다. 임의의 큰 수를 거리로 돌려주거나 이전에 찾은 다른 경로를 대신 돌려주면 받는 쪽이 진짜 답과 구별할 수 없게 됩니다.

비용

BFS는 O(V + E), 힙을 쓴 Dijkstra 알고리즘은 O((V + E) log V)입니다. 경로를 확인하는 path_cost는 간선 딕셔너리를 만드는 데 O(E), 경로를 확인하는 데 경로 길이만큼 걸립니다. 같은 지도에서 여러 경로를 확인한다면 간선 딕셔너리를 한 번만 만들어 두고 다시 쓰면 됩니다. 이 딕셔너리는 같은 출발지와 도착지 사이에 간선이 하나뿐이라고 가정합니다.

모든 단순 경로를 나열하는 방법은 길의 수만큼 시간이 들어서, 정점이 많아지면 길의 수가 폭발적으로 늘어납니다. 모든 정점 쌍 사이에 간선이 있는 지도라면 정점이 10개만 되어도 단순 경로가 10만 개를 넘습니다. 그래서 이 방법은 실제로 길을 찾는 데 쓰지 않고, 작은 입력에서 빠른 알고리즘을 확인하는 데만 씁니다. 빠르고 복잡한 방법과 느리지만 단순한 방법을 함께 두고 서로 확인하게 하는 것은 이 교재 전체에서 되풀이한 방법입니다.

정리

• 길 찾기 프로그램을 짜기 전에 "가장 좋은 길"이 간선의 개수가 가장 적은 길인지, 비용의 합이 가장 적은 길인지를 먼저 정하고 반환할 값의 단위를 적어 둡니다.
• 간선의 개수는 BFS, 음수가 아닌 비용의 합은 Dijkstra 알고리즘이 최소로 만들며, 같은 지도에서도 두 답이 다를 수 있습니다.
• 반환한 경로가 시작과 끝이 맞고, 이어진 간선이 모두 지도에 있고, 비용의 합이 알려 준 거리와 같은지를 알고리즘과 상관없이 확인할 수 있습니다.
• 가장 좋은 경로인지는 작은 지도에서 모든 단순 경로를 나열하는 기준 구현과 비교해 확인하고, 무작위 지도로 여러 번 비교합니다.
• 닿을 수 없는 정점은 무한대 거리와 빈 경로로 알리며, 받는 쪽이 이 경우를 따로 처리해야 합니다.

연습 문제

1. 바로 가는 길이 빨라지면

S→T의 시간을 12분에서 1분으로 바꾸면 두 요구의 답은 각각 어떻게 될까요?

2. 닿을 수 없는 목적지

목적지에 닿을 수 없을 때, 길 찾기 함수를 부르는 쪽은 결과를 어떻게 다루면 좋을까요? 피해야 할 처리도 함께 생각해 보세요.

3. 음수 비용이 생기면

B→A의 비용이 할인 때문에 -2가 되었다고 합시다. 본문의 dijkstra에 이 지도를 넣으면 어떻게 되고, 최단 비용은 어떤 방법으로 구하면 될까요?

다음 글 알고리즘 선택·검사 입력·다음 학습에서는 문제를 보고 어떤 알고리즘을 고를지 판단하는 질문들을 정리하고, 검사할 입력을 고르는 방법과 이 교재 다음에 공부할 거리를 소개합니다.