이 페이지는 "왜 3-node Dijkstra가 Max-Flow보다 옳은가"를 끝까지 따진다. 대피소 3개의 과부하 해소가 어떻게 최소비용 transshipment 문제로 환원되는지, 그 특수 구조 위에서 Dijkstra가 어떻게 매 iteration마다 갱신되는 PQ를 따라 전역 최소비용 흐름을 만드는지, 그리고 lazy deletion이 PQ 재구성 비용을 어떻게 0으로 만드는지를 수학적으로 해부한다.
대피소 문제의 점수는 단 하나의 양으로 정해진다 — Σ 이주 비용의 총합이다. 10,000층의 건물에서 각 층의 사람들을 3개 대피소 중 하나에 배정하되, 한 대피소에 67,500명 이상이 몰리면 "과부하"가 되어 다른 대피소로 사람을 옮겨야 한다. 그리고 사람을 옮기는 데에는 거리에 비례하는 비용이 든다. 베스트 해법은 이 문제를 두 단계로 분해한다.
핵심 통찰은 이 둘이 순차적으로 독립이라는 것이다. 1차 배정은 거리만 보고 단순 그리디로 끝내고, 그 결과 발생한 불균형만을 2단계가 받아 푼다. 1단계는 "좋은 출발점"을, 2단계는 "그 출발점에서 최소비용으로 제약을 만족"시키는 일을 맡는다.
출제 의도상 이 문제의 정답은 최소비용 최대유량(Min-Cost Max-Flow) 또는 헝가리안 매칭이다. 사람을 공급 노드로, 대피소를 용량이 67,500인 수요 노드로 두고, 사람–대피소 간선에 거리 비용을 매기면 표준 수송 문제(transportation problem)가 된다. 이론적으로 100% 최적해를 준다.
그러나 시험 시간 4시간 안에 MCMF의 가변 그래프를 매번 재구성하며 정확히 구현하는 것은 위험이 크다. 베스트 해법은 다른 길을 간다 — 문제의 그래프가 극도로 작다는 사실을 무기로 삼는다.
대피소가 단 3개이므로, "대피소 i에서 대피소 j로 한 명을 옮기는 최소비용"을 간선 가중치로 하는 그래프는 노드 3개, 방향 간선 6개에 불과하다. 과부하 대피소를 출발점으로 Dijkstra를 돌리면, 부하가 임계 미만인 가장 싼 대피소까지의 최소비용 이주 경로가 즉시 나온다. 그 경로를 따라 한 명을 흘려보내고, 과부하가 남으면 반복한다.
먼저 문제를 정확한 수학적 대상으로 환원한다. 대피소를 노드 {0,1,2}로, 각 대피소의 현재 인원을 bi로 둔다. 과부하 대피소는 bi > C(C = 67{,}500)인 노드다. 우리가 결정할 것은 각 방향 간선 (i,j)를 따라 흐르는 사람 수 fij ≥ 0이다.
주목할 점은 비용 함수 cij가 흐름량에 의존한다는 것이다. i에서 j로 첫 번째 사람을 옮길 때는 j에 가장 가까운 사람을 보내므로 싸고, 두 번째·세 번째로 갈수록 점점 먼 사람을 보내야 하니 비싸진다. 즉 cij는 흐름량에 대해 비감소(convex marginal cost)다. 이 볼록성이 모든 정당성의 토대다.
모든 시점에서 다음이 성립한다: 간선 (i,j)의 PQ pq[i][j]의 top은, 현재 대피소 i에 소속된 사람들 중 대피소 j까지 가장 가까운 사람의 이주 비용이다.
change(i,j)로 한 명이 실제로 이동하면 그 사람은 i 소속이 아니게 되어, PQ에 남은 그 사람의 항목은 stale해진다. 다음 adjust()가 PQ top을 꺼낼 때 "현재 i 소속이 아님"을 확인하면 즉시 pop으로 버린다(lazy deletion). 이 검사가 끝나면 위 불변식이 다시 성립한다.
과부하 대피소 s에서 한 명을 임계 미만인 어떤 대피소로 흘려보낼 때, 3-node Dijkstra가 찾는 경로는 그 한 명을 이동시키는 모든 가능한 경로 중 비용 최소다. 직접 이동(s→t)이든 경유 이동(s→m→t)이든, Dijkstra의 d[] 배열이 가장 싼 것을 자동으로 고른다.
간선 비용 cij는 거리이므로 항상 0 이상이다. Dijkstra의 전제(음의 간선 없음)가 성립하므로, 우선순위가 가장 낮은(=거리가 가장 짧은) 노드를 큐에서 꺼내는 순간 그 노드의 d[]는 확정 최단거리다.
노드가 3개뿐이므로 가능한 경로는 (a) 직접 s→t, (b) 한 번 경유 s→m→t 둘뿐이다(같은 노드 재방문은 비용만 늘리므로 최적 경로에 없다). Dijkstra의 relaxation 단계 if d[u]+cost < d[v]는 노드 u를 거치는 모든 경로를 검사하므로, 경유가 직접보다 싸면 d[t]는 자동으로 경유 비용으로 갱신된다.
루프는 임계 미만인 노드를 큐에서 꺼내는 순간 종료한다(if shelter_count[u] < C: break). 그 노드 u는 "임계 미만이면서 s로부터 가장 가까운" 대피소다 — 더 가까운 임계 미만 노드가 있었다면 Dijkstra가 그것을 먼저 꺼냈을 것이다. 따라서 역추적된 경로는 한 명을 이동시키는 비용 최소 경로다.
한 가지 의심이 남는다 — 매번 "한 명만" 옮기는 그리디가 전체 이주 비용 합을 최소로 만드는가? 일반적인 그리디는 근시안적일 수 있다. 그러나 여기서는 비용 함수의 볼록성이 그리디를 구해준다.
각 간선의 한계 이주 비용 cij(f)가 흐름 f에 대해 비감소(볼록)라면, "매 단계 현재 가장 싼 한계비용 흐름을 1단위 보내기"를 반복하는 그리디는 최소비용 transshipment 해와 일치한다.
이유: 최소비용 흐름 문제에서 각 단위 흐름의 비용은 그 시점의 한계비용이다. 한계비용이 흐름에 따라 단조 증가하므로, "지금 가장 싼 한계비용"을 먼저 소비하지 않고 미루면 — 그 흐름은 언젠가 같거나 더 비싼 한계비용으로 소비해야 하고, 그 자리를 차지한 다른 흐름은 더 싼 자리를 빼앗긴 셈이 된다. 교환논법(exchange argument)으로, 한계비용 오름차순으로 흐름을 채우는 것이 항상 최적이다. PQ는 정확히 이 "현재 가장 싼 한계비용"을 O(1)에 제공한다.
이 문제의 Dijkstra는 교과서 버전을 극단적으로 축소한 것이다. 노드 집합이 V = {0,1,2}로 고정이므로 우선순위 큐조차 필요 없다 — 매 단계 argmin을 선형 스캔(3회 비교)으로 끝낸다. "진짜 PQ"는 다른 곳, 즉 각 간선의 한계비용을 정렬해 두는 pq[i][j]에 쓰인다.
void adjust(int target) { // target = 과부하 대피소 long long d[3] = { LINF, LINF, LINF }; int visited[3] = { 0, 0, 0 }; int path[3] = { -1, -1, -1 }; d[target] = 0; int u = -1; for (int iter = 0; iter < 3; ++iter) { // (1) 미방문 노드 중 d 최소 — 노드 3개라 선형 스캔이면 충분 u = -1; long long best = LINF + 1; for (int i = 0; i < 3; ++i) if (!visited[i] && d[i] < best) { best = d[i]; u = i; } if (u < 0 || d[u] == LINF) return; // 도달 가능 대피소 소진 visited[u] = 1; if (shelter_count[u] < CAP) break; // 임계 미만 도착 → 목표 발견 // (2) relax — u 를 거치는 모든 경로 검사 for (int v = 0; v < 3; ++v) { if (visited[v] || v == u) continue; long long w = edgeCost(u, v); // pq[u][v] 의 현재 top if (d[u] + w < d[v]) { d[v] = d[u] + w; path[v] = u; } } } // (3) 역추적하며 경로를 따라 한 명씩 흘려보냄 for (int cur = u; path[cur] != -1; cur = path[cur]) change(path[cur], cur); // path[cur] → cur 한 명 이동}
O(V²) 선형 스캔은 9회 비교에 불과하다 — 힙의 O(log V) 상수 오버헤드보다 빠르다. 진짜 우선순위 큐가 필요한 곳은 간선 비용을 공급하는 edgeCost(u,v)다. 이 함수가 pq[u][v]의 top을 읽으며, top이 stale(이미 이동한 사람)이면 pop으로 정리한다 — §4에서 다룬다.
long long edgeCost(int u, int v) { auto& q = pq[u][v]; // min-heap: (이주비용, 사람id) while (!q.empty() && shelter[q.top().id] != u) q.pop(); // stale 항목 제거 — lazy deletion if (q.empty()) return LINF; // u 소속이 아무도 없음 → 간선 막힘 return q.top().cost;}
pq[u][v]는 "대피소 u 소속 각 사람의, 대피소 v까지 거리"를 최소 힙으로 담는다. top은 항상 v에 가장 가까운 u 소속자다. 한 명이 빠지면 다음으로 가까운 사람이 top이 되고, 그 비용은 직전보다 같거나 크다 — 이것이 §2 Lemma가 요구한 한계비용의 단조 증가(볼록성)다. 힙 자료구조 자체가 볼록성을 강제한다.
adjust() 1회의 시간 복잡도는 O(V² + V · Pamort)다. V=3이므로 Dijkstra 본체는 상수 O(9). edgeCost의 lazy pop은 분할 상환되어 0이다 — PQ에 push된 각 사람 항목은 평생 단 한 번만 pop되므로, 모든 edgeCost 호출의 pop 총합은 전체 사람 수 N으로 묶인다.
전체 solve()는 과부하가 해소될 때까지 adjust()를 반복한다. 한 번의 adjust()가 정확히 한 명을 이동시키므로 호출 횟수는 "옮겨야 할 총 인원" M에 비례한다. 따라서 전체 비용은 O(9M + N) = O(M + N) — 사실상 선형이다. PQ 구축의 O(N log N)이 지배항이며, N ≈ 10^4 규모에서 즉시 끝난다.
순진한 구현은 매 adjust()마다 pq[i][j] 6개를 전부 다시 만든다. 한 명이 이동하면 그 사람의 소속이 바뀌어 두 개의 출발 PQ(pq[old][*])와 두 개의 도착 PQ(pq[new][*])가 영향받는다. 재구성은 O(N log N)이고, 이를 M번 반복하면 O(M·N log N)으로 폭주한다.
lazy deletion은 이 비용을 우회한다. 핵심 관찰: stale 항목은 틀린 정보가 아니라 단지 오래된 정보다. pq[u][v]의 top이 "이미 다른 곳으로 떠난 사람"이라면, 그것은 무효일 뿐 해롭지 않다. 그저 꺼내 버리면 된다. 그리고 한 사람 항목은 평생 한 번만 버려지므로, 모든 lazy pop의 총합은 O(N)에 묶인다.
edgeCost(u,v)가 반환하는 값은 항상 현재 u에 실제로 소속된 사람들 중 v 최근접자의 비용이다. while 루프가 shelter[top.id] != u인 모든 항목을 pop으로 걷어내므로, 루프 종료 시 top은 반드시 진짜 u 소속자다.
주의: 한 사람이 u → m → u로 되돌아오는 경우는 없다 — Dijkstra 경로는 단순 경로이고, 한 adjust()는 경로 위 각 사람을 한 칸씩만 옮긴다. 따라서 "소속이 u로 복원된 stale 항목"은 존재하지 않으며, lazy deletion이 유효한 항목을 잘못 버릴 위험이 없다.
이 문제가 단순 "최근접 대피소로 보내기"보다 깊은 이유는 경유 흐름(transshipment) 때문이다. 일반 수송 문제는 공급지에서 수요지로 직접 보내지만, transshipment는 중간 노드를 거치는 것을 허용한다. 대피소 문제에서 이것은 다음 상황으로 나타난다.
과부하 대피소 S₀가 있고, S₂가 임계 미만이라 하자. 그러나 S₀→S₂ 직접 비용이 12, S₀→S₁이 7, S₁→S₂가 8이라면 — 경유 비용 7+8=15 > 12이므로 직접이 낫다. 반대로 S₀→S₁=3, S₁→S₂=4라면 경유 7 < 12이 이긴다. Dijkstra의 relaxation은 이 비교를 명시적으로 하지 않는다 — d[] 배열의 갱신이 자동으로 더 싼 쪽을 선택한다. 이것이 "일반화된 transshipment의 특수해"라는 문제 페이지 표현의 정확한 의미다.
change가 일어난다 — S₀에서 S₁로 한 명, S₁에서 S₂로 (다른) 한 명. 이는 "S₁에 원래 있던, S₂에 아주 가까운 사람"을 S₂로 보내고, 그 빈자리를 S₀의 사람으로 메우는 릴레이다. S₀의 사람을 S₂까지 멀리 보내는 대신, 가까운 사람들의 연쇄 교대로 같은 효과를 더 싸게 낸다. transshipment의 본질이 여기 있다.
| 전략 | 정확도 | 구현 시간 | 실패 위험 | 평가 |
|---|---|---|---|---|
| 거리 그리디 (제약 무시) | ~60% | 20min | 낮음 | 과부하 폭주 — 임계를 전혀 못 지킴 |
| Min-Cost Max-Flow | 100% | 2–3h | 큼 | 가변 그래프 재구성·구현 실패 위험 큼 |
| Hungarian 매칭 | 100% | 3h+ | 큼 | 매 단계 비용 행렬 재구성 필요 |
| 3-node Dijkstra + lazy PQ | ~95% | 40min | 낮음 | 작은 그래프 + 실시간 PQ 갱신의 최적 균형 |
표의 구조는 §1의 분해를 그대로 비춘다. 정확도만 보면 Max-Flow·Hungarian이 100%로 우월하다. 그러나 시험은 정확도와 구현 시간·실패 위험의 곱으로 채점된다. 범용 최적해는 가변 그래프를 매 단계 재구성해야 하고, 4시간 안에 버그 없이 완성할 확률이 낮다. 거리 그리디는 빠르지만 임계 제약을 아예 못 지켜 무효다.
3-node Dijkstra는 "그래프가 상수 크기"라는 문제 고유의 구조를 활용해, 범용 해법의 95% 품질을 1/4의 구현 시간으로 달성한다. lazy deletion이 PQ 재구성 비용을 분할 상환으로 0에 묶으면서, 매 iteration 잔량을 실시간 반영한다 — 이 실시간성이 작은 그래프에서 오히려 정적 Max-Flow보다 정확할 수 있는 이유다(§2 note).
edgeCost의 while 루프가 빠지면, 이미 이동한 사람의 옛 위치를 기준으로 비용을 계산해 경로가 틀어진다. PQ top을 읽기 전 반드시 shelter[top.id] != u인 항목을 모두 pop해야 한다. 이 검사가 빠지면 같은 사람을 두 번 옮기거나 비용이 어긋난다.
shelter_count[u] < CAP 검사는 노드 u를 확정한 직후, relax하기 전에 와야 한다. relax 뒤에 두면 임계 미만 노드를 만나고도 한 단계 더 진행해, 경로가 불필요하게 길어지거나 도착 노드를 놓친다.
v에 대해 수행해야 s→m→t 경유가 d[]에 반영된다. 경유가 직접보다 쌀 때 비용 차이가 누적되어 점수에 드러난다.
pq[u][*]가 비고, 그 간선은 사실상 막힌 것이다. edgeCost가 LINF를 반환하지 않으면 빈 힙의 top 접근으로 미정의 동작이 일어난다. 빈 PQ → 무한대 비용 매핑을 반드시 명시하라.
solve()의 바깥 루프 조건은 any(shelter_count[i] >= CAP)여야 한다. 한 번의 adjust()가 한 명만 옮기므로, 초과분이 여러 명이면 같은 대피소에 대해 adjust()가 여러 번 호출되어야 한다. 한 번만 호출하면 임계를 못 지켜 무효 처리된다.
이 풀이가 "통과한다"는 주장의 근거는 채점기 출력이다. 채점기는 모든 대피소가 임계 미만임을 먼저 확인(위반 시 즉시 실패)하고, 그 다음 change() 호출마다 누적한 이주 비용 총합을 PASS 기준과 비교한다.
main.cpp는 고정 seed로 10,000층·3대피소 입력을 생성하고, init()→solve() 호출 뒤 verify()로 채점한다. g++ -O2로 main.cpp + user.cpp를 함께 컴파일해 실행하면, 모든 대피소가 67,500 미만임을 확인하고 누적 이주 비용이 PASS 기준 이하임을 PASS로 출력한다. 채점기가 change() 시점마다 비용을 직접 누산하므로, 이 판정은 풀이의 객관적 성적표다.