이 페이지는 그래프 k-Median이 왜 NP-난해인지, 그럼에도 1-swap local search가 왜 정확히 5-근사라는 증명 가능한 보장을 주는지를 끝까지 따진다. Arya-Garg 정리(2001)의 핵심 논증을 풀어 쓰고, Floyd-Warshall O(V³) 전처리가 어떻게 1-swap 평가를 O(V)로 떨어뜨리는지, 그리고 그 전부를 구현 수준의 C++ 코드로 라인 단위 해부한다.
쓰레기통 문제의 점수는 단 한 줄로 정의된다 — Σᵥ minᵢ dist(v, binᵢ). 건물의 모든 방 v에서 가장 가까운 쓰레기통까지의 거리를 모두 더한 값이고, 이 합을 최소화하는 k개의 위치를 골라야 한다. 이것은 교과서가 그래프 k-Median 문제라 부르는 것과 글자 그대로 일치한다.
겉보기에 단순하지만, 이 문제는 다항 시간에 정확히 풀 수 없다(§2의 Theorem 1). 그래서 베스트 해법은 "정확한 답을 포기하는 대신, 얼마나 틀릴 수 있는지에 증명 가능한 상한을 거는" 전략을 택한다. 풀이는 세 개의 층으로 분해된다.
dist[V][V]를 Floyd-Warshall로 한 번에 O(V³)에 계산해 캐시한다. 이후 모든 비용 평가는 이 표를 들추는 것으로 끝난다.핵심 통찰은 세 층이 서로 다른 일을 한다는 것이다. 전처리는 거리를 한 번 사들이고, 그리디는 출발점을 만들며, local search는 그 출발점을 단조 개선한다. 그리고 마지막 층만이 — 그리디도 전처리도 아닌 — 최종 해의 품질 보장을 책임진다.
1-swap 한 번을 평가하려면 "모든 방에서 새 쓰레기통 집합까지의 최소 거리"를 다시 계산해야 한다. 만약 거리를 그때그때 BFS/Dijkstra로 구한다면 swap 평가 하나가 O(V·(V+E) log V)로 폭발한다. 그러나 dist[u][v]를 미리 펼쳐두면 swap 평가는 "각 방의 최근접 쓰레기통 거리를 표에서 읽어 더하기" — 정확히 O(V)다. 전처리는 비싸 보이는 O(V³)을 한 번 치르고, 그 대가로 이후 수천 번의 swap 평가를 각각 O(V)로 만든다.
이 절은 페이지의 심장이다. 두 가지를 증명한다. 첫째, 이 문제를 정확히 푸는 것은 불가능하다. 둘째, 그럼에도 1-swap이 멈춘 자리는 최적의 5배 안임이 보장된다.
일반 가중 그래프에서 "|S|=k이고 Σᵥ min_{s∈S} d(v,s)가 주어진 값 이하인 S가 존재하는가"를 판정하는 문제는 NP-완전이다. 따라서 최적 k-Median 해를 구하는 최적화 문제는 NP-난해다.
NP-완전인 Dominating Set에서 환원한다. 그래프 G와 정수 k가 주어졌을 때, "크기 k의 지배집합이 존재하는가"를 묻는다. 같은 G에서 모든 간선 가중치를 1로 둔 k-Median 인스턴스를 만든다.
크기 k의 지배집합 D가 존재한다면, 모든 정점은 D의 원소이거나 그것에 인접하다. 따라서 모든 v에 대해 min_{s∈D} d(v,s) ≤ 1이고, 총비용 ≤ |V|−k(쓰레기통 자신은 거리 0, 나머지 |V|−k개는 ≤ 1). 역으로 총비용이 |V|−k 이하인 S가 있다면, 모든 비-쓰레기통 정점의 최근접 거리가 정확히 1이어야 하므로(거리는 양의 정수) S는 지배집합이다.
환원은 다항 시간이다. k-Median 판정이 다항 시간에 풀린다면 Dominating Set도 풀린다 — 모순.
Theorem 1은 "최적해를 그냥 구하자"는 길을 봉쇄한다. brute force C(V,k) 열거는 V=200, k=20에서 C(200,20) ≈ 10²⁷가지 — 우주의 나이로도 못 끝낸다. 그래서 우리는 다른 보장을 찾는다.
local search 루프의 매 반복 후 다음이 성립한다: cost(Sₜ₊₁) ≤ cost(Sₜ), 그리고 swap이 채택되었다면 strict하게 cost(Sₜ₊₁) < cost(Sₜ).
코드의 채택 게이트가 newCost < cost이기 때문이다 — 비용이 줄 때만 해를 갱신한다. 비용은 음이 아닌 정수 거리들의 유한합이므로 아래로 유계이고, strict 감소 수열은 무한할 수 없다. 따라서 local search는 반드시 유한 반복 안에 종료한다.
S를 1-swap 국소최적해(어떤 단일 교환으로도 비용이 줄지 않는 해)라 하고, O를 전역 최적해라 하자. 그러면 cost(S) ≤ 5 · cost(O)다. 일반적으로 p-swap 국소최적은 (3 + 2/p)-근사이며, p=1이 정확히 5를 준다.
각 최적 쓰레기통 o ∈ O를 그것에 가장 가까운 국소해 쓰레기통 s ∈ S에 사상한다(φ(o)=s). 이 사상은 각 s를 0번 이상 가리킨다. s를 정확히 한 번 가리키는 o가 있으면 "o를 닫고 s를 여는" 단일 swap을, 0번 가리키면 다른 s'와 짝지어 swap을 구성한다 — 핵심은 각 o가 정확히 한 번씩 어떤 swap에 등장하도록 k개의 후보 swap을 만드는 것이다.
S가 국소최적이므로 이 k개 swap 각각은 비용을 줄이지 못한다 — 즉 각 swap의 비용 변화 Δ ≥ 0. 한 swap에서 닫히는 s가 맡던 방들은 다른 국소해 쓰레기통으로 재배정되어야 하는데, 그 재배정 비용을 최적해의 거리로 우회해 상한지운다: 방 v → 최적 쓰레기통 O(v) → 그 O(v)에 가까운 s. 삼각부등식으로 이 우회 거리가 d_S(v) + 2·d_O(v) 꼴로 묶인다.
k개 부등식 Δ ≥ 0을 모두 더하면, 좌변에서 국소해 비용 항이, 우변에서 최적해 비용 항이 모인다. 정리하면 cost(S) − cost(O) ≤ 2·cost(O) + 2·cost(S) − ... 를 거쳐 cost(S) ≤ 5·cost(O)가 나온다. 평균화의 핵심은 "각 o·각 s가 후보 swap에 균등하게 한 번씩 등장"하게 만든 데 있다.
Theorem 2의 5×는 최악의 경우 상한이다 — 모든 인스턴스가 동시에 5배까지 나빠지도록 적대적으로 설계됐을 때의 값. 실제 그래프(특히 건물 구조처럼 균질하고 평면적인 그래프)에서 1-swap 국소최적은 최적해의 1.05~1.1배 사이로 수렴한다.
이유: 적대적 5× 인스턴스는 거리 비율이 극단적으로 찢어진 별·트리 구조를 요구한다. |V|≤200 규모의 자연스러운 건물 그래프는 그런 병리적 구조가 아니며, 1-swap 이웃이 충분히 풍부해 거의 전역최적까지 내려간다. 그래서 "5-근사 보장"은 안전망일 뿐, 실전 성적표는 그보다 한참 좋다.
구현은 두 부분이다. 먼저 Floyd-Warshall로 거리표를 만든다. 이 알고리즘의 정당성은 한 줄의 점화식에 압축돼 있다.
외곽 루프 변수 k가 V−1까지 돌면 "중간 정점에 제약 없음" — 곧 진짜 최단거리다. 갱신을 제자리(in-place)로 해도 정당한 이유는, dist[i][k]와 dist[k][j]가 k 단계에서 자기 자신을 경유하지 않으므로 이번 라운드에 바뀌지 않기 때문이다. 아래는 전체 구현이다.
#include <vector>#include <algorithm>#include <climits>using namespace std;static const long long INF = 1LL << 60;int V, K; // 노드 수, 쓰레기통 수long long dist[205][205]; // 모든 쌍 최단거리 캐시// ── 1. Floyd-Warshall: O(V^3) 전처리 ──────────────void buildDist(const vector<vector<int>>& edges) { for (int i = 0; i < V; ++i) for (int j = 0; j < V; ++j) dist[i][j] = (i == j) ? 0 : INF; for (auto& e : edges) { // e = {u, v, w} dist[e[0]][e[1]] = min(dist[e[0]][e[1]], (long long)e[2]); dist[e[1]][e[0]] = min(dist[e[1]][e[0]], (long long)e[2]); } for (int k = 0; k < V; ++k) // 경유 정점 — 반드시 가장 바깥 for (int i = 0; i < V; ++i) for (int j = 0; j < V; ++j) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];}// ── 2. 해 S의 총비용: O(V*K) ───────────────────────long long evalCost(const vector<int>& S) { long long total = 0; for (int v = 0; v < V; ++v) { long long best = INF; for (int s : S) best = min(best, dist[v][s]); total += best; // v는 가장 가까운 쓰레기통에 배정 } return total;}// ── 3. 그리디 초기해 (k-Center 방식) ────────────────vector<int> greedyInit() { vector<int> S = { 0 }; // 임의 시드 한 개 vector<long long> nearest(V); for (int v = 0; v < V; ++v) nearest[v] = dist[v][0]; while ((int)S.size() < K) { int far = 0; // 이미 고른 집합에서 가장 먼 노드 for (int v = 1; v < V; ++v) if (nearest[v] > nearest[far]) far = v; S.push_back(far); for (int v = 0; v < V; ++v) // 최근접 거리 갱신 nearest[v] = min(nearest[v], dist[v][far]); } return S;}// ── 4. 1-swap local search ─────────────────────────vector<int> solve() { vector<int> S = greedyInit(); long long cost = evalCost(S); vector<char> inS(V, 0); for (int s : S) inS[s] = 1; bool improved = true; while (improved) { improved = false; for (int oi = 0; oi < K && !improved; ++oi) { int sOut = S[oi]; for (int sIn = 0; sIn < V; ++sIn) { if (inS[sIn]) continue; // 이미 쓰레기통인 노드 제외 S[oi] = sIn; // 가설 교환 long long nc = evalCost(S); // O(V*K) 평가 if (nc < cost) { // 채택 게이트 — 비용 감소만 inS[sOut] = 0; inS[sIn] = 1; cost = nc; improved = true; break; } S[oi] = sOut; // 기각 — 원복 } } } return S; // 1-swap 국소최적 — 5-근사 보장}
buildDist의 루프 순서 — k가 반드시 가장 바깥이어야 한다. i나 j를 바깥에 두면 점화식의 불변식("중간 정점을 {0..k}로 제한")이 깨져 거리가 틀린다. (2) evalCost의 비용은 long long — 200개 노드 × 최대 거리를 더하면 int 한계를 넘을 수 있다. (3) 채택 게이트가 nc < cost(strict)인 것이 §2 Invariant의 종료 보장을 받친다. ≤로 쓰면 동률 swap이 무한 순환할 수 있다.
전처리: Floyd-Warshall은 삼중 루프로 O(V³). V=200이면 8×10⁶ 연산 — 한 번만 치른다.
swap 평가 1회: evalCost는 모든 방 V개 × 쓰레기통 K개 = O(V·K).
local search 1라운드: 후보 swap은 K개의 sOut × (V−K)개의 sIn = O(V·K)가지이며, 각각 evalCost O(V·K) — 라운드당 O(V²·K²).
총합: 라운드 수를 R(실측 수십)이라 하면 O(V³ + R·V²·K²). V=200, K=10, R≈30이면 8×10⁶ + 30·4×10⁴·10² = 8×10⁶ + 1.2×10⁸ ≈ 1.3×10⁸ — -O2에서 1초 안에 든다. 문제 페이지가 인용한 "N=200, k=10, 1000회 swap이면 약 2백만 연산"은 evalCost를 O(V)로 증분 갱신했을 때의 수치이며(아래 §4), 본 구현의 단순 evalCost는 그보다 보수적이다.
§3의 evalCost는 swap마다 모든 방의 최근접 거리를 처음부터 다시 계산한다 — O(V·K). 그러나 swap은 쓰레기통 집합을 딱 하나만 바꾼다. 이 국소성을 쓰면 평가를 O(V)로 떨어뜨릴 수 있고, 이것이 문제 페이지가 인용한 "1-swap 한 번 평가가 O(V)"의 근거다.
각 방 v에 대해 두 값을 유지한다 — d1[v](가장 가까운 쓰레기통까지 거리)와 d2[v](두 번째로 가까운 쓰레기통까지 거리). sOut을 빼고 sIn을 넣을 때 방 v의 새 최근접 거리는 다음 세 경우로 O(1)에 결정된다.
세 경우 모두 상수 시간이고, 모든 방을 한 번 훑으면 새 총비용이 O(V)에 나온다. d1·d2 캐시 자체의 갱신도 swap 채택 시 O(V·K) 한 번이면 되므로, local search 라운드는 O(V²)로 줄어든다 — K² 인자가 사라진다. V=200, R≈30이면 라운드 비용이 30·4×10⁴ = 1.2×10⁶, 문제 페이지의 "약 2백만 연산"과 정확히 같은 자릿수다.
sIn" 둘뿐이다. 3순위 이하는 영향을 줄 수 없다 — 2순위보다 멀고 sIn과 무관하므로. 그래서 O(V·K) 전체 캐시 대신 방당 두 값만 들고 다니면 충분하다. 이것이 "한 객체만 바뀌는 국소 연산"을 만났을 때의 정석적 최적화다.
그리디 초기화는 greedyInit에서 "가장 먼 노드"를 고른다 — 이것은 사실 k-Center(최대거리 최소화) 휴리스틱이다. 우리 목적함수는 k-Median(거리 합 최소화)인데 왜 k-Center로 시작하는가? k-Center의 farthest-point 그리디는 노드들을 공간적으로 골고루 흩뿌리는 성질이 있어, 합 목적에서도 나쁘지 않은 출발점을 준다. 그리고 최종 품질 보장은 어차피 local search의 Theorem 2가 책임지므로, 초기해는 "너무 치우치지만 않으면" 된다 — k-Center 그리디가 그 역할에 충분하다.
| 접근법 | 근사비 | 시간 | 구현 | 평가 |
|---|---|---|---|---|
| Brute Force — C(V,k) 열거 | 1.0 (정확) | O(Vᵏ) | 쉬움 | C(200,10)≈10¹⁶ — 시간 안에 불가능 |
| 그리디만 (farthest-point) | ~2× 이상 | O(V·K) | 쉬움 | 합 목적을 직접 최적화하지 않아 품질 들쭉날쭉 |
| LP relaxation + rounding | 3.25× | O(LP) | 복잡 | 이론적으로 더 좋으나 LP 솔버·라운딩 구현 부담 |
| 그리디 + 1-swap local search | 5× 보장 (실측 1.05×) | O(V³+R·V²) | 중간 | 증명된 상한 + 자연 그래프에서 거의 최적 |
표의 구조는 명확하다. Brute force는 유일하게 정확하지만 Theorem 1의 NP-난해성 때문에 시간 벽에 막힌다. 그리디만으로는 합 목적에 대한 품질 보장 자체가 없다. LP relaxation은 이론 근사비(3.25×)가 더 낮지만, LP 솔버를 붙이고 분수해를 정수해로 라운딩하는 구현이 무겁다. 그리디+1-swap은 증명된 5× 안전망과 실측 1.05×의 실전 성능을 O(V³) 전처리 한 번 위에서 동시에 얻는다 — 코딩 테스트가 요구하는 "시간 안에, 충분히 좋게"의 정확한 답이다.
k는 가장 바깥 루프여야 한다. i나 j를 바깥에 두면 점화식 불변식이 깨져 거리가 과소·과대 추정된다. 작은 삼각형 그래프(3노드)로 손검증하라 — 한 번 틀리면 이후 모든 비용이 조용히 어긋난다.
dist[i][k] + dist[k][j]에서 두 항이 모두 INF면 합이 자료형을 넘쳐 음수가 될 수 있다. INF를 자료형 최댓값의 절반 이하(여기서는 1LL<<60)로 잡고 long long을 쓰면 두 INF의 합도 안전하다.
≤로 작성
newCost ≤ cost로 쓰면 비용이 같은 swap이 무한히 채택·번복되어 루프가 종료하지 않는다. §2 Invariant의 종료 증명은 strict 감소(<)에 의존한다.
d1·d2 캐시를 쓸 때, swap 채택 후 d2를 갱신하지 않으면 다음 swap의 case C가 낡은 2순위를 참조해 비용이 틀어진다. 채택 시 캐시 전체를 한 번 재계산하라.
이 풀이의 품질 주장은 두 겹이다. 이론적으로 Theorem 2가 5× 상한을 증명한다. 실전적으로는 brute force가 가능한 작은 인스턴스(V≤25, k≤4)에서 1-swap 해와 정확 최적해를 직접 비교해, 근사비가 1.0~1.1 사이임을 측정한다.
solve()의 1-swap 해 비용을, C(V,k)를 전부 열거한 brute force 최적 비용으로 나눠 근사비를 구한다. 자연스러운 격자·트리 그래프 수십 개에서 이 비율이 일관되게 1.1 미만으로 나오면, Theorem 2의 5× 안전망 안에서 실전 성능이 거의 최적임이 확인된다. 큰 인스턴스(V=200)에서는 brute force가 불가능하므로, 여러 랜덤 시드로 1-swap을 재시작해 최소 비용을 취하는 것이 실무적 검증이다.