§ 1문제 정의
10,000층의 건물에서 매 층마다 사람들을 3개의 대피소 중 하나에 배정한다. 한 대피소에 67,500명 이상이 몰리면 “과부하”이고, 다른 대피소로 분산시켜야 한다. 단, 사람을 옮기는 데에는 비용이 든다 — 가까운 사람부터 옮길수록 싸다.
겉으로는 거리 기반 배정 문제처럼 보이지만 실은 최대 유량(Max-Flow) 또는 헝가리안 매칭이 의도된 정답이다. 그러나 시험 시간 4시간 안에는 구현이 어렵다.
실전 베스트 풀이는 다른 길을 간다. 대피소 i → j 로의 한 명 이동 최소비용을 priority queue로 미리 정렬해두고, 과부하 대피소에서 시작해 “비용이 최소인 인접 대피소”로 한 명씩 흘려보낸다. 이때 노드는 단 3개. 3-노드 Dijkstra면 충분하다.
3개 노드 그래프에서의 Dijkstra는 우아하다 — 헝가리안의 결과를 90% 비용으로 95% 정확도로 흉내 낸다.
§ 2핵심 시뮬레이션 — adjust(target) 동작
과부하 상태의 대피소 target에서 시작해, 부하가 낮은 대피소까지 “가장 싼 이주 경로”를 찾고, 그 경로를 따라 사람을 한 칸씩 옮긴다. 노드는 단 3개라 Dijkstra가 거의 즉시 끝난다.
FIG. 15 — Dijkstra on 3-shelter transition graph
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3왜 이게 최적인가
의도된 정답인 Max-Flow / Hungarian과 비교하면 트레이드오프가 명확하다:
| 접근법 | 정확도 | 구현 시간 | 실전 평가 |
|---|---|---|---|
| Max-Flow | 100% | 2–3h | 구현 실패 위험 큼 |
| Hungarian | 100% | 3h+ | 매트릭스 재구성 매번 필요 |
| 3-node Dijkstra | ~95% | 40min | ✓ 최적 선택 |
| 거리 그리디 | ~60% | 20min | 과부하 폭주 |
3-node Dijkstra가 작은 그래프에서 최적인 이유:
- 대피소가 단 3개 → 노드 3, 엣지 6. Dijkstra가 O(N²)=9 연산.
- 이주 비용 = 가장 가까운 한 명. Priority Queue로 O(1) lookup.
- 경로 길이는 최대 3 (직접 또는 1번 경유) — 한 번 흘려보낼 때마다 균형이 즉시 회복된다.
- 중간 노드 경유가 직접 이동보다 싸면 자동으로 거기로 흐름. 일반화된 transshipment의 특수해.
큰 그래프에선 Max-Flow가 옳지만, 3개 노드에선 Dijkstra가 오히려 더 정확하다 — 매 iteration마다 PQ 정렬이 실시간으로 갱신되기 때문.
§ 4알고리즘 골격
init():
# 각 사람을 가장 가까운 대피소에 1차 배정
for ant in ants:
shelter[ant] = nearest_shelter(ant.floor)
# 대피소 i → j 이주 비용 PQ 구축
for i in 0..2: for j in 0..2: if i != j:
for ant in shelter[i]:
pq[i][j].push(cost = dist(ant, shelter[j]))
solve():
while any(shelter_count[i] >= 67500):
target = argmax(shelter_count)
adjust(target)
adjust(target): # 3-node Dijkstra
d[3] = [INF, INF, INF]; d[target] = 0
visited[3] = [0,0,0]; path[3] = [-1,-1,-1]
for _ in 0..2:
u = argmin(d[i] for i where !visited[i])
visited[u] = 1
if shelter_count[u] < 67500: break # 도착!
for v in 0..2 if !visited[v]:
cost = pq[u][v].top().cost
if d[u] + cost < d[v]:
d[v] = d[u] + cost
path[v] = u
# 역추적하며 한 명씩 흘려보내기
cur = u
while cur != target:
change(path[cur], cur) # 한 명 이동
cur = path[cur]
PQ 유지의 묘미: change()로 한 명이 이동하면 그 사람의 정보가 PQ들에서 stale 데이터가 된다. 다음 adjust() 시작 시 PQ top이 “현재 그 대피소 소속”이 아니면 pop으로 제거 — lazy deletion. 매번 PQ를 재구성하는 비용을 피한다.