가중 그래프: 간선에 비용이 붙을 때

"BFS는 모든 도로를 한 걸음으로 쳐. 그런데 진짜 지도에는 짧은 골목도 있고 긴 고속도로도 있잖아. 간선마다 비용이 달라지는 순간 '도로를 가장 적게 지나는 길'이 '가장 짧은 여정'을 뜻하지 않게 돼."

간선이 숫자를 짊어져

가중 그래프는 간선마다 숫자를 붙여. 거리일 수도, 시간일 수도, 가격이나 용량이나 확률일 수도 있지. 그리고 그 숫자를 어떻게 결합할지는 문제마다 달라. 거리와 비용은 대개 더하지만, 경로의 대역폭은 병목을 봐야 하니 최솟값을 취하고, 확률은 곱하거나 음의 로그로 바꿔 쓰기도 해. "가중치가 있다"가 곧 "전부 더해서 최소를 구한다"는 뜻은 아니야.

왜 이게 BFS를 깨뜨릴까

BFS는 간선 수가 가장 적은 경로를 찾는데, 그건 모든 간선의 비용이 같을 때만 맞는 답이야. 이렇게 그려 봐. A→B는 길이 100짜리 도로 하나고, A→C→D→B는 다 합쳐 6인 짧은 도로 셋이야. BFS는 거쳐 가는 간선 수만 세니까 간선 하나짜리 A→B를 '최단'이라고 선언하고 100만큼 돌아가는 길로 보내 버려. 간선이 가장 적은 경로와 비용이 가장 싼 경로가 갈라진 거지. 가중치를 제대로 다루려면 총비용을 누적하면서 언제나 지금까지 가장 싼 경계 노드를 다음에 펼치는 알고리즘이 필요해. 그게 Dijkstra고, 힙 트랙에서 만든 우선순위 큐 위에 얹혀 있어. '지금 가장 싼 걸 달라'는 바로 그 구조 말이야.

가중 그래프는 간선마다 비용을 달고 있어서, 최단 경로는 간선 수가 가장 적은 게 아니라 가중치 총합이 가장 낮은 경로야. 간선 수를 세는 BFS는 여기서 틀려. 가중 최단 경로에는 우선순위 큐로 굴러가는 Dijkstra 같은, 비용을 아는 알고리즘이 필요해.

가중 문제의 가문

가중치가 붙으면 고전 문제 한 무리가 통째로 열려. 이 트랙이 그 핵심을 훑어.

단일 출발 최단 경로. 한 시작점에서 모든 곳까지 가장 싼 경로를 구해. 가중치가 0 이상이면 Dijkstra, 음수가 섞이면 Bellman-Ford고, 바로 다음 두 꼭지에서 다뤄.
연결성. union-find로 '이거 이어져 있나?'에 답하고, 다른 알고리즘의 부품으로도 들어가.
최소 신장 트리. 전부를 잇는 가장 싼 방법이야. Kruskal과 Prim이 있고.
모든 쌍 최단 경로(Floyd-Warshall). 모든 정점 쌍 사이의 가장 싼 경로인데, 이름은 알아둘 만하고 여기서 구현하진 않아.

하나같이 '가중치가 붙은 네트워크 위에서의 최적화'고, 다 합치면 라우팅과 네트워크 설계, 스케줄링, 클러스터링을 덮어. 실제 시스템에서 아주 큰 덩어리지.

피파의 고백

가중치가 붙은 지도에서 두 지점 사이를 BFS로 라우팅한 적이 있어. 결과는 기술적으로 '두 번만 거치는' 경로였는데 한참을 돌아가더라. 짧은 옆길 몇 개 대신 고속도로를 탄 셈이었지. 아빠가 내가 무시하고 있던 가중치를 가리켰어. "BFS 는 마일이 아니라 도로를 세고 있어." 해결책은 더 똑똑한 BFS가 아니었어. 마일을 더하는 완전히 다른 알고리즘, 그러니까 Dijkstra였지. 최저 비용을 원하면서 최소 간선을 고른 게 범주 자체를 잘못 짚은 거였고, 가중치가 바로 그 실수가 물어뜯는 자리야.

Code

간선이 가장 적은 게 가장 싼 건 아니야·python

# 가중 그래프: 인접 리스트에 (neighbor, weight) 저장.
weighted = {
    "A": [("B", 100), ("C", 2)],
    "C": [("D", 2)],
    "D": [("B", 2)],
    "B": [],
}

# 최소 엣지로 (BFS 가 찾는 것): A -> B, 딱 1 hop... 근데 비용 100.
# 최저 비용으로 (우리가 실제 원하는 것): A -> C -> D -> B, 3 hop, 비용 6.

def path_cost(graph, path):
    total = 0
    for u, v in zip(path, path[1:]):
        total += dict(graph[u])[v]    # 엣지 u->v 의 무게
    return total

print("A->B  (fewest edges):", path_cost(weighted, ["A", "B"]))          # 100
print("A->C->D->B (cheapest):", path_cost(weighted, ["A", "C", "D", "B"]))  # 6
# BFS 는 1-엣지 경로 (비용 100) 를 골라. 가장 싼 경로가 엣지가 더 많아.
# 그래서 가중 그래프는 BFS 가 아니라 Dijkstra 가 필요해.

Exercise

가중 그래프에 간선 A→B(비용 10), A→C(비용 3), C→B(비용 3)이 있어. A에서 B로 가는 최소 간선 경로와 그 비용, 그다음 최저 비용 경로와 그 비용을 찾아 봐. BFS는 어느 쪽을 반환할까? 그리고 간선이 이동 시간을 나타낸다면 그게 왜 틀린 답이지?

Hint

간선이 가장 적은 건 A→B로 한 번에 가는 거고 비용은 10이야. 가장 싼 건 A→C→B로 두 번 거치고 비용이 6이고. BFS는 A→B를 반환하는데, 총 이동 시간이 중요하다면 틀린 답이지. 두 번 거치는 쪽이 실제로 더 빠르니까. 가중치가 있으면 거치는 횟수가 아니라 비용을 더해야 해.

간선이 숫자를 짊어져

왜 이게 BFS를 깨뜨릴까

가중 문제의 가문

피파의 고백

Code

External links

Exercise

Progress

댓글 0