§ 1문제 정의
통과 조건: 도로 상태 + repairNum ≥ (10 + 화물 무게). 비용은 (10 + repairNum × 총 무게). repair는 일종의 ‘추가 통행료’지만 미래에도 영향을 준다 — 보강된 도로는 다음 트럭에게 더 싸다.
이 문제는 단순한 최단경로가 아니다. ‘이 도로를 지금 수리하면, 나중에 다시 지나갈 때 공짜다’ — 그래프의 미래 비용을 고려한 라우팅이 필요. 보통 다익스트라 변형 + 화물 군집 라우팅 + 도로 상태 캐시.
적재/하역 비용은 무게의 제곱이라 무거운 화물은 한 번 들면 가능한 한 곧장 배달해야 한다 — 매번 짐을 내렸다 다시 싣는 패턴은 비싸다.
repair는 통행료가 아니다 — 미래 트럭에게 주는 선물이다.
§ 2예제 시각화 — 7도시, 9도로
FIG. 12 — repair-aware routing, road status decays/grows
STEP 01 / 5
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
strategy:
# 화물을 출발지가 가까운 묶음으로 그룹화
cluster freights by source city
for each cluster:
# 가장 좋은 차주 도시 → 화물 적재 (w² 비용)
load(f)
# 도로 상태가 부족하면 repair 최소값으로 통과
# 비용 = 10 + repairNum × (10 + weight)
path = dijkstra_with_repair(src, dest, weight)
for road in path:
move(road, max(0, weight + 10 - status))
unload()