노후화된도로는 원본 자료에 grader의 move·load·unload 함수와 ROAD·Freight 구조체만 공개돼 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 라인 단위 코드 해부 대신 — grader가 실제로 어떻게 점수를 누산하는지를 정밀하게 역설계하고, 그 비용 모델 위에서 "도로 보수 비용을 간선 가중치로 환산한 최단경로"라는 베스트 해법을 설계하고 정당성을 논증한다. 코드는 의사코드와 핵심 부분의 C++ 스케치로 제시하며, 추측이 들어가는 곳은 "설계 제안"임을 명시한다.
다른 문제와 달리 노후화된도로의 grader는 점수를 누산하는 함수 본문(move·load·unload)을 통째로 공개한다. 이것은 거대한 단서다 — 점수 공식을 추측할 필요가 없다. 우리는 grader 코드를 읽어서 비용 모델을 확정하고, 그 위에서 해법을 연역한다.
CITY_NUM = 1000개 도시와 ROAD_NUM = 3000개 무방향 도로. init()이 도시 순열을 셔플하며 경로(path)들을 이어 붙이므로 그래프는 연결(connected)이 보장된다 — 모든 화물의 출발지→목적지 경로가 존재한다.FREIGHT_NUM = 2000개. 각 화물은 {pos, dest, weight}를 가지며 weight ∈ [1, 90].Truck.freight는 단일 포인터). 초기 위치는 도시 0.weight² — load()와 unload()가 동일하게 gTotalScore += weight*weight를 더한다. 한 화물을 끝까지 옮기면 적재 1회 + 하역 1회로 고정 비용 2·weight²이 발생한다.10 + repairNum·totalWeight. 여기서 totalWeight = 10 + freightWeight(빈 트럭이면 10).repairNum + status ≥ totalWeight. 부족하면 move()가 false를 반환하고 트럭은 움직이지 않는다.repairNum + status ≤ 1000 — 보수는 무한정 못 한다.score()가 모든 화물의 pos == dest를 확인할 때 통과. SCORE를 최소로 만든다. 미배달 화물이 있으면 PENALTY 10¹².move()의 마지막 한 줄 mroads[mRoadID].status += (repairNum - totalWeight)가 이 문제의 심장이다. 도로를 지나갈 때마다 상태는 totalWeight만큼 닳고, 동시에 내가 투자한 repairNum만큼 회복된다. 만약 repairNum > totalWeight로 "넉넉히" 보수하면 도로는 영구적으로 더 튼튼해지고, 그 이득은 다음 트럭이 거저 가져간다. 보수는 통행료가 아니라 그래프에 대한 자본 투자다.
이 통찰에서 베스트 해법의 골격이 세 부분으로 정해진다.
이 분해는 로봇청소기(№ 01)가 "이동 최적화"와 "정보 최적화"를 분리했던 정신과 같다 — 한 화물의 최단경로(국소)와 2000개의 배달 순서·보수 정책(전역)을 독립된 관심사로 떼어내면 각각을 따로 공략할 수 있다.
먼저 한 화물 하나를 옮기는 문제로 좁힌다. 무게 w인 화물이 도시 s에서 t로 가야 한다. 이 화물의 totalWeight는 W = w + 10으로 고정이다. 이때 각 도로의 통과 비용을 정의하면 — 문제가 표준 최단경로로 환원된다.
무게 W인 트럭이 상태 σ인 도로를 통과할 때, 통과를 성립시키는 최소 repairNum은 다음으로 유일하게 결정된다: repair*(σ, W) = max(0, W − σ).
repairNum + σ ≥ W가 통과 조건이므로 repairNum ≥ W − σ. 음수는 무의미하니 하한은 max(0, W−σ)다. 그리고 이동 비용 10 + repairNum·W는 repairNum에 단조 증가하므로, "지금 이 화물을 통과시키는 것"만 본다면 최소값을 쓰는 것이 항상 이득이다. 초과 보수는 §4에서 별도로 다룬다.
도로 e마다 위 cost(e)를 간선 가중치로 부여하면, 무게 W인 화물을 s→t로 옮기는 최소 이동 비용 경로는 그 가중 그래프의 단일 출발점 최단경로와 정확히 일치한다. 모든 cost(e) ≥ 10 > 0이므로 음의 간선이 없고, 다익스트라가 적용 가능하다.
한 화물을 옮기는 동안 load·unload 비용 2w²는 경로 선택과 무관한 상수다(어느 경로를 타든 적재 1회·하역 1회). 따라서 경로 선택은 오직 move() 비용의 합만 좌우한다.
한 화물이 통과하는 동안 — 다른 트럭이 끼어들지 않는 한 — 도로 상태 σ_e는 그 화물이 그 도로를 처음 밟는 순간에만 평가된다. 화물 하나가 같은 도로를 두 번 밟는 최적 경로는 없으므로(단순 경로가 항상 더 싸다, cost > 0), 경로의 총 이동 비용은 Σ_{e∈path} cost(e)로 경로를 따라 가산적이다.
가산적이고 비음인 간선 비용의 최소합 경로 — 이것이 곧 다익스트라가 푸는 문제다. 우선순위 큐에서 처음 확정된 노드의 거리가 최단거리임은 음의 간선이 없다는 사실(cost ≥ 10)에서 보장된다.
move()는 repairNum + status > 1000이면 통과를 거부한다. 어떤 도로의 상태 σ가 매우 낮고 무게 W가 커서 max(0,W−σ) + σ > 1000이 되면 — 그 도로는 이 화물로는 아예 통과 불가다. 비용 환산 시 그런 도로는 가중치 ∞(간선 제거)로 처리해야 한다. 실제로는 W ≤ 100(무게≤90 + 10)이고 상태 초기값이 100~399이므로 대부분 통과 가능하지만, 여러 트럭이 같은 도로를 닳게 한 뒤에는 σ가 음수까지 떨어질 수 있어 — 이 가드는 반드시 필요하다.
풀이 코드가 없으므로 전체 골격은 의사코드로, 비용 환산의 핵심부만 C++로 스케치한다. 전략은 "한 화물씩, 매번 그 화물의 무게로 그래프를 환산해 다익스트라"이다. 도로 상태는 move()가 갱신한 뒤 getRoadInfo()로 다시 읽어 다음 화물에 반영한다.
// 베스트 해법 골격 — 비용 환산 다익스트라 + 화물 순차 배달
process():
getRoadInfo(roads) // 3000개 도로 현재 상태
getFreightInfo(freights) // 2000개 화물
order = sort_freights(freights) // §4: 배달 순서 정책
for f in order:
// (1) 트럭을 화물 출발지로 이동 — 빈 트럭(totalWeight=10)
path0 = dijkstra(truck.pos, f.pos, W=10, roads)
drive(path0, W=10)
// (2) 화물 적재 — 비용 w²
load(f.id)
// (3) 적재 상태로 목적지까지 — 무게 W = f.weight + 10
path1 = dijkstra(f.pos, f.dest, W=f.weight+10, roads)
drive(path1, W=f.weight+10)
// (4) 하역 — 비용 w²
unload()
getRoadInfo(roads) // 상태 변동 재동기화
// 한 도로 통과 — 통과 가능성 확인 후 최소 보수로
drive(path, W):
for road in path:
repair = max(0, W - road.status)
move(road.id, repair) // 비용 10 + repair·W
핵심은 다익스트라가 쓰는 간선 가중치 함수다. 설계 제안 — grader가 노출한 비용 공식을 그대로 옮긴 것이므로 이 부분은 추측이 아니라 확정이다. 무게 W에 의존하므로 화물마다 다익스트라를 새로 돌린다.
// 도로 e를 무게 W로 통과하는 비용 — grader 공식 그대로static const long long INF = 1e18;long long edgeCost(int status, int W) { int repair = (W > status) ? (W - status) : 0; if (repair + status > 1000) return INF; // 상태 한도 초과 → 통과 불가 return (long long)10 + (long long)repair * W;}// 무게 W로 src에서 모든 도시까지 최소 이동비용 — 다익스트라void dijkstra(int src, int W, Road roads[], long long dist[], int prevRoad[]) { for (int i = 0; i < CITY_NUM; ++i) { dist[i] = INF; prevRoad[i] = -1; } dist[src] = 0; MinHeap pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 낡은 큐 항목 폐기 for (int ei : adj[u]) { // u에 붙은 도로들 int v = other(roads[ei], u); long long w = edgeCost(roads[ei].status, W); if (w >= INF) continue; // 통과 불가 도로 스킵 if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; prevRoad[v] = ei; // 경로 역추적용 pq.push({dist[v], v}); } } }}
edgeCost는 grader의 move() 본문을 그대로 옮긴 것이다 — score = 10 + repairNum·totalWeight, totalWeight가 곧 우리의 W다. 빈 트럭으로 출발지까지 가는 구간은 W=10, 적재 후 구간은 W = weight+10으로 다익스트라를 두 번 돌린다. prevRoad[]로 경로를 역추적해 move()를 순서대로 호출한다. d > dist[u] 스킵은 거리 갱신 시 큐를 갱신하지 않고 재삽입하는 표준 다익스트라의 정확성 가드다 — 로봇청소기 № 01의 visited==vcnt 스킵과 같은 역할이다.
도시 V = 1000, 도로 E = 3000. 이진 힙 다익스트라 1회는 O((V+E)\log V) ≈ 4000·10 = 4×10⁴ 연산. 화물 하나당 다익스트라를 2회(출발지 이동 + 적재 후) 돌리므로 화물당 ~8×10⁴, 화물 2000개 전체는 ~1.6×10⁸ 연산이다. TC가 최대 100개라면 ~10¹⁰까지 늘어 시간이 빠듯해질 수 있다 — §5에서 이 비용을 줄이는 대안을 다룬다. 그래프가 화물마다 무게에 따라 가중치가 바뀌므로, 전(全) 쌍 최단경로를 한 번 계산해 재사용하는 단순 캐싱은 불가능하다는 점이 이 문제의 계산 부담의 본질이다.
§2·§3은 "한 화물을 어떻게 옮기는가"를 풀었다. 그러나 SCORE를 진짜로 좌우하는 두 전역 결정이 남아 있다 — 2000개를 어떤 순서로 옮길 것인가, 그리고 최소 보수를 넘어선 초과 보수를 언제 할 것인가.
한 화물의 load/unload 비용 2w²와 적재 후 경로 비용은 순서를 어떻게 바꿔도 거의 불변이다(상태 변동을 무시하면). 순서가 진짜로 좌우하는 것은 — 하역을 마친 도시에서 다음 화물의 출발지까지 빈 트럭으로 이동하는 비용이다. 이것은 정확히 물류배송(№ 03)·배달기사(№ 14)의 구조다.
따라서 설계 제안은: 현재 트럭 위치에서 가장 가까운 출발지를 가진 화물을 다음으로 고르는 최근접 이웃(NN) 순서다. 설계 제안 — 더 정교하게는, 출발지가 같은 도시에서 나가는 화물끼리 묶어(clustering) 빈 트럭 회송을 분할 상각한다.
도로 e를 무게 W로 통과한 직후 상태는 σ_e ← σ_e + (repairNum − W)로 갱신된다. 만약 항상 최소 보수 repairNum = max(0, W−σ_e)만 한다면:
· σ_e ≥ W였던 경우: repairNum=0, 갱신 후 σ_e − W — 상태가 닳는다.
· σ_e < W였던 경우: repairNum = W−σ_e, 갱신 후 σ_e + (W−σ_e) − W = 0 — 상태가 0으로 떨어진다.
즉 최소 보수만 하면 자주 쓰이는 도로는 상태가 계속 닳아 0 이하로 내려가고, 다음 트럭은 매번 풀 보수 비용을 문다. 이것이 "초과 보수"를 고려해야 하는 이유다.
초과 보수의 amortization 논증. 어떤 도로 e가 앞으로 k개의 트럭(평균 무게 \bar W)에 의해 통과될 것이라 하자. 매번 최소 보수만 하면 — 첫 통과 후 상태가 낮게 깔리고, 이후 k−1회 통과는 각각 약 \bar W만큼의 보수 비용을 문다. 누적 보수 비용은 대략 (k−1)·\bar W·\bar W다.
반대로 첫 통과 때 한 번에 k·\bar W만큼 크게 보수하면(상태 한도 1000 안에서) — 도로 상태가 충분히 높아져 이후 k−1회 통과는 보수 0으로 지나간다. 이때 초과 보수 비용은 첫 통과에 한 번 몰린 ≈ (k−1)·\bar W 단위의 repairNum에 그 시점 트럭 무게를 곱한 양이다. 한 번의 큰 투자가 k−1번의 반복 비용을 흡수하는 — 전형적인 amortized 분석 구조다.
k를 정확히 모르는 이상 초과 보수는 도박이며 — grader 점수 공식이 공개돼 실제 교통량 분포를 측정하기 전까지는, "최소 보수 + 선택적 초과 보수"의 경계는 재튜닝 대상이다.
| 전략 | 완전성 | 비용 경향 | 계산량 | 평가 |
|---|---|---|---|---|
| 홉 수 최소 (BFS) | 보장 | 높음 | 낮음 | 도로 보수 비용을 무시 — 약한 도로를 비싸게 보수하며 지난다 |
| 고정 가중 최단경로 | 보장 | 중간 | 낮음 | 무게 의존성을 무시 — 무거운 화물 비용을 과소평가 |
| 전(全)화물 동시 최적화 (MCMF류) | 보장 | 최소 | 불가 | 상태가 통과마다 변하는 동적 비용 — 정적 흐름 모델로 안 잡힌다 |
| 무게별 비용 환산 다익스트라 + NN 순서 | 보장 | 낮음 | 중간 | grader 공식을 그대로 환산 — 화물당 정확한 최소 이동비용 |
표는 설계 비교다 — 측정된 점수가 아니라 각 전략이 SCORE에 어떻게 작용하는지를 정리한다. 홉 수 최소(BFS)는 가장 단순하지만 도로 보수 비용을 통째로 무시해, 약한 도로를 골라 비싸게 보수하며 지나는 최악의 경로를 고를 수 있다. 고정 가중 최단경로는 한 발 낫지만 — 비용이 repair·W로 무게에 곱해진다는 사실을 못 담는다. 무거운 화물일수록 보수 비용이 무게 배로 커지므로, 가중치는 반드시 화물 무게마다 다시 계산돼야 한다(Theorem 1). 전(全)화물을 한 번에 최적화하는 최소비용흐름(MCMF) 류는 이론적으로 매력적이나 — 도로 상태가 통과할 때마다 변하는 동적 비용이라 정적 흐름 모델에 들어맞지 않는다. 따라서 "무게별 비용 환산 다익스트라 + NN 배달 순서"가 §2 Theorem 1(정확한 환원)과 §4(순서·보수 정책)를 모두 만족하는 최선의 후보다. 계산량이 부담되면(Theorem 2) — 무게를 몇 개 구간으로 양자화해 같은 구간 화물끼리 다익스트라 결과를 재사용하는 것이 현실적 절충이다.
move()는 totalWeight = 10 + freight->weight다 — 트럭 자체 무게 10이 항상 더해진다. 빈 트럭도 totalWeight=10으로 움직인다. 비용 환산에서 W에 이 +10을 빠뜨리면 통과 조건 판정과 비용이 모두 어긋난다.
move()는 통과한 도로의 status를 영구히 바꾼다. 한 화물을 옮긴 뒤 getRoadInfo()로 상태를 다시 읽지 않으면, 다음 화물의 다익스트라가 낡은 상태로 잘못된 경로를 고른다. 매 화물 후 재동기화하라.
repairNum + status > 1000이면 move()는 false를 반환한다. 비용 환산 시 그런 도로를 ∞로 막지 않으면, 다익스트라가 통과 불가 경로를 "최단"으로 골라 — 트럭이 멈춰 화물이 미배달로 남고 PENALTY 10¹²를 맞는다.
load()는 트럭에 이미 화물이 있거나(freight != nullptr) 트럭 위치가 화물 위치와 다르면 실패한다. 적재 전 반드시 unload가 끝났고 트럭이 정확히 f.pos에 있는지 — 다익스트라 경로가 출발지에서 끝나는지 확인하라.
k(앞으로의 통과 횟수)를 모르는 이상 이득을 보장할 수 없다. 점수 공식과 실제 교통량 분포가 측정되기 전까지 초과 보수의 경계는 재튜닝 대상임을 분명히 하라.
01번과 달리 이 페이지는 측정된 SCORE를 제시할 수 없다 — 검증된 통과 코드가 없기 때문이다. 다만 노후화된도로는 grader가 비용 함수 본문을 공개하므로, 다른 설계 페이지보다 검증 기반이 단단하다: 비용 모델은 추측이 아니라 grader 코드에서 직접 도출된 사실이다. 정직한 검증 기준은 — 설계가 grader의 확정 제약(통과 조건·상태 갱신·상태 한도)과 모순되지 않는가이다.
move() 비용 공식으로부터 베스트 해법을 설계하고 그 정당성을 논증한 것이다. "무게별 비용 환산 → 다익스트라 최단경로 → NN 배달 순서"라는 골격은 grader 코드에서 직접 연역된 확정 사실(Theorem 1) 위에 서 있고, 초과 보수의 amortization(§4)만이 미래 교통량 예측을 요구하는 설계 제안이다. 이 페이지의 가치는 정답 코드가 아니라 — "grader가 비용 함수를 공개했을 때, 그 함수를 어떻게 간선 가중치로 환산해 표준 최단경로 문제로 환원하는가"라는 사고의 골격에 있다.