가중 그래프: 엣지에 비용이 있을 때

"BFS 는 모든 도로를 한 걸음으로 대해. 근데 진짜 지도엔 짧은 길이랑 긴 고속도로가 있어 — 엣지가 다른 비용을 싣는 순간, '최소 도로' 가 '최단 여정' 을 뜻하길 멈춰."

엣지가 숫자를 키운다

가중 그래프는 각 엣지에 숫자를 붙여: 거리, 이동 시간, 가격, 대역폭, 확률. 갑자기 '최단 경로가 뭐야?' 가 더 풍부한 답을 가져 — 최소 엣지가 아니라 최저 총 무게 경로야. 인접 리스트엔, 이웃 옆에 무게를 저장해: {"A": [("B", 5), ("C", 1)], ...}. 그래프 구조는 같고; 각 엣지가 이제 비용을 실어.

왜 이게 BFS 를 깨나

BFS 는 최소 엣지 경로를 찾는데, 모든 엣지가 같은 비용일 때만 맞아. 그려봐: A→B 는 길이 100 의 도로 하나, A→C→D→B 는 총 6 의 짧은 도로 셋. BFS 는, hop 을 세서, A→B 를 엣지 하나로 '최단' 이라 선언하고 — 100 단위 우회로 보내. 최소-엣지 경로랑 최저-비용 경로가 갈렸어. 가중치를 다루려면, 총 비용을 누적하고 늘 지금까지 가장 싼 frontier 노드를 다음에 확장하는 알고리즘이 필요해. 그게 Dijkstra 고, Heaps 트랙의 우선순위 큐 위에 지어졌어 — '늘 현재 가장 싼 거 줘' 의 구조.

가중 그래프는 각 엣지에 비용을 둬, 그래서 최단 경로는 최소 엣지가 아니라 최저 *총* 무게야. BFS (hop 세기) 는 여기서 틀려; 가중 최단 경로는 우선순위 큐로 굴러가는 Dijkstra 같은 비용-인식 알고리즘이 필요해.

가중 문제의 가문

가중치가 고전 문제 가문 전체를 열고, 이 트랙이 핵심을 투어해:

단일 출발 최단 경로: 한 시작에서 모든 곳까지 가장 싼 경로. Dijkstra (음 아닌 무게) 또는 Bellman-Ford (음수 다룸) — 다음 두 lesson.
연결성: union-find, '이거 연결됐어?' 와 building block 으로.
최소 신장 트리: 모든 걸 연결하는 가장 싼 방법 — Kruskal 이랑 Prim.
전쌍 최단 경로 (Floyd-Warshall): 모든 쌍 사이 가장 싼 경로 — 알아둘 이름, 여기선 구현 안 해.

이것들 하나하나가 '가중 네트워크 위 최적화' 고, 함께 라우팅, 네트워크 설계, 스케줄링, 클러스터링을 덮어 — 실제 시스템의 거대한 조각.

피파의 고백

한 번 가중 지도에서 두 지점 사이 라우팅에 BFS 를 썼는데 기술적으론 '두 hop' 이지만 멀리 돌아가는 경로를 얻었어 — 옆길 몇 개가 짧은데 고속도로로. 아빠가 내가 무시한 무게를 가리켰어: "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, 1 hop, 비용 10. 최저 비용: A→C→B, 2 hop, 비용 6. BFS 는 A→B (한 hop) 반환 — 총 이동 시간이 중요하면 틀려, 두-hop 경로가 사실 더 빠르니까. 가중 = hop 세기 아니라 비용 합.

엣지가 숫자를 키운다

왜 이게 BFS 를 깨나

가중 문제의 가문

피파의 고백

Code

External links

Exercise

Progress

댓글 0