이 페이지는 "왜 파워를 점진적으로 키우는가"를 끝까지 따진다. scan 비용이 power³이라는 사실에서 출발해, Union-Find로 같은 방 장치를 병합하는 정확성, 작은 파워부터 차례로 던지는 휴리스틱이 비용 함수의 볼록성 위에서 왜 최적에 가까운가, 195파워 보정 단계가 무엇을 잡는가, radix sort 결과 정렬의 역할을 PASS CUT 21B 위에서 해부한다.
IoT가전 문제의 점수 gTotalCost는 모든 scan_device 호출 비용의 합이며, 1회 호출 비용은 scanPower³이다. 최대 256개 장치를 "같은 방끼리" 정확히 그룹핑해야 하고(틀리면 PENALTY 10조), 점수는 "그 그룹핑을 알아내는 데 스캔을 얼마나 싸게 했는가"다.
비용 함수의 형태 — 세제곱 — 이 모든 설계를 지배한다. 파워 1000으로 한 번 스캔하면 10억, 파워 100이면 100만, 파워 30이면 27,000. 즉 파워를 10배 키우면 비용은 1000배가 된다. 강한 파워는 멀리·벽 너머까지 장치를 탐지하지만 압도적으로 비싸다. 베스트 해법의 목표는 가능한 한 약한 파워로 같은 방 판정을 끝내고, 강한 파워는 꼭 필요할 때만 쓰는 것이다.
풀이는 세 단계로 분해된다.
getID로 1..N의 작은 인덱스로 재번호한다. 각 장치를 자기 자신을 루트로 하는 단독 집합으로 초기화한다.powerList = {30, 60, 100, 300, 600, 1000}의 파워를 약한 것부터 차례로 쓴다. 각 파워 단계에서 아직 그룹에 안 묶인 장치들을 시작점으로 scan_device를 호출하고, "같은 방" 판정이 서면 Union으로 병합한다.mDeviceIds에 채운다.채점기의 scan_device는 탐지된 각 장치에 대해 power, tx, ty를 돌려준다. user 코드는 getRet(t) = t.power + |t.tx| + |t.ty|를 계산해 이것이 스캔에 쓴 파워와 정확히 같은지 본다. 이 등식이 성립하면 두 장치는 같은 방에 있다는 신호다 — 신호가 감쇠 없이 온전히 도달했다는 뜻이기 때문이다. 이 한 줄의 판정식이 알고리즘의 지능을 압축한다.
먼저 가장 강한 제약을 확인한다: 이 풀이는 모든 장치를 올바른 방으로 그룹핑하는가? 채점기 verify는 user가 채운 deviceIds가 원래 방 구성과 다르면 PENALTY 10조를 부과한다.
scan 함수 실행 중 매 시점에 다음이 성립한다: 두 장치 a, b가 같은 Find 루트를 가진다 ⇔ 지금까지의 Union 연산으로 a와 b가 한 동치류에 속함.
Union-Find는 동치 관계의 세 성질 — 반사·대칭·추이 — 을 구조적으로 보장한다. 특히 추이성: a~b이고 b~c이면 a~c가 — Union을 명시적으로 호출하지 않아도 — Find가 같은 루트를 반환함으로써 자동 성립한다.
"같은 방"이라는 관계는 동치 관계다(반사·대칭·추이). 모든 "같은 방" 쌍을 Union으로 합치면, Union-Find의 동치류는 정확히 방 구성과 일치한다 — 즉 각 동치류가 하나의 방이다.
"장치 a와 b가 같은 방에 있다"는 관계 R을 보자. 반사성(a는 a와 같은 방)·대칭성(a~b이면 b~a)은 자명하다. 추이성: a와 b가 같은 방, b와 c가 같은 방이면 — 방은 장치들의 분할이므로 — a와 c도 같은 방이다. 따라서 R은 동치 관계다.
동치 관계는 집합을 동치류들로 분할하며, 이 분할이 곧 방 구성이다. Union-Find는 호출된 Union들의 동치 폐포(transitive closure)를 정확히 계산하므로(Invariant), "탐지된 모든 같은 방 쌍"에 Union을 호출하면 동치류 = 방이 된다. 핵심 조건은 같은 방의 모든 쌍을 빠짐없이 발견하는 것 — 이것이 §3·§4에서 점진 파워 + 195 보정이 책임지는 부분이다.
정확성이 보장되었으니 이제 점수다. 같은 방 판정을 위한 스캔 파워 순서가 비용을 결정한다.
비용 함수 f(p) = p³은 p > 0에서 볼록이다(2계도함수 6p > 0). 볼록성의 직접 귀결: 같은 "탐지 범위"를 약한 파워 여러 번으로 나눠 얻을 수 있다면, 한 번의 강한 파워보다 — 또는 불필요하게 강한 파워보다 — 비용이 작다.
구체적으로, 같은 방 장치 대부분이 파워 30·60·100으로 판정된다면 그 비용은 27,000 ~ 10⁶ 수준이다. 같은 판정을 일괄 파워 1000으로 하면 호출당 10⁹ — 세 자릿수 비싸다. 약한 파워가 처리할 수 있는 쌍을 강한 파워로 처리하는 것은 순수한 낭비다.
파워를 {30, 60, 100, 300, 600, 1000} 오름차순으로 쓰고, 아직 어떤 그룹에도 안 묶인 장치만 새 스캔 시작점으로 삼으면, 각 같은 방 쌍은 그것을 판정할 수 있는 가장 약한 파워에서 병합된다. 더 강한 파워 단계에 도달할 즈음엔 약한 파워로 처리 가능한 쌍이 이미 모두 묶여 있으므로, 강한(비싼) 스캔 호출 수가 최소가 된다.
코드의 바깥 루프는 powerList를 약→강 순서로 순회한다. 각 파워 단계에서 안쪽 루프는 j = 1..idcnt의 장치를 시작점으로 scan_device를 호출하는데, idcnt는 "지금까지 등장(getID로 재번호)한 장치 수"다. 두 루프 모두 idcnt < N 조건을 단다 — 모든 장치가 한 번이라도 탐지돼 등장하면 즉시 루프를 빠져나간다.
약한 파워로 충분히 많은 장치가 서로를 탐지하면 idcnt가 빠르게 N에 도달하고, 강한 파워 단계는 아예 실행되지 않는다. 강한 파워가 실행되는 경우는 "약한 파워로는 도저히 닿지 않는, 벽 너머 멀리 떨어진 장치"가 남았을 때뿐 — 정확히 강한 파워가 필요한 경우다. 따라서 각 쌍은 자신을 판정 가능한 최소 파워에서 처리되고, 비싼 호출은 불가피한 만큼만 발생한다.
calcuate_power는 신호가 벽(#)을 지날 때마다 파워와 거리 성분을 절반으로 깎는다. 벽이 없으면 파워는 거리만큼 1씩만 줄고, 탐지 결과의 power + |tx| + |ty|는 — 깎인 거리 성분이 tx,ty로 보정돼 — 원래 쏜 파워와 정확히 같게 복원된다. getRet == power는 곧 "신호 경로에 벽이 없었다 = 같은 방"의 판정식이다. 코드가 추가로 detected.power > 1을 요구하는 것은, 파워가 1까지 닳은 경계 신호의 오판을 막기 위한 안전 가드다.
이 문제는 본질적으로 온라인 연결성 질의다. 상태와 비용을 형식적으로 적으면 다음과 같다.
채점기의 장치 ID는 누적 난수라 거대하고 듬성듬성하다. getID는 ID를 하위 비트로 해시(key & MASK)해 체인(st[], next[])에 넣고, 처음 보는 ID에는 1부터 차례로 작은 인덱스를 부여한다. 이 작은 인덱스가 Union-Find 배열의 첨자가 된다.
아래는 풀이의 심장부, scan 함수의 점진 파워 병합 루프다. PASS를 만든 구현 그대로다.
void scan(int mDeviceId, int mTotalDevice) { N = mTotalDevice; idcnt = 0; for (int i = 0; i < LM; ++i) root[i] = i, st[i] = 0; // 각 장치 = 단독 집합 getID(mDeviceId); // 시작 장치를 인덱스 1로 등록 int i, j, k, power; for (i = 0; i < 6 && idcnt < N; ++i) { // 약→강 파워, 모두 등장하면 조기종료 power = powerList[i]; // 30, 60, 100, 300, 600, 1000 for (j = 1; j <= idcnt && idcnt < N; ++j) { // 등장한 장치를 시작점으로 dcnt = scan_device(keys[j], power, detected); // 비용 power³ 청구 for (k = 0; k < dcnt; ++k) { int rid = getID(detected[k].id); // 탐지된 장치 재번호(미등장이면 새 인덱스) if (detected[k].power > 1 && getRet(detected[k]) == power) Union(j, rid); // 벽 없음 = 같은 방 → 병합 } } } power = 195; // 보정 단계 — §4 참조 for (i = 1; i <= idcnt; ++i) { if (i != root[i]) continue; // 각 그룹 대표(루트)만 재스캔 dcnt = scan_device(keys[i], power, detected); for (j = 0; j < dcnt; ++j) { if (getRet(detected[j]) == power) Union(i, getID(detected[j].id)); // 갈라진 같은 방 재결합 } }}
idcnt < N 조건이 §2 Theorem 2의 조기 종료를 구현한다. getID는 새로 탐지된 장치를 그 자리에서 등장 처리(idcnt++)하므로, 약한 파워 스캔이 새 장치를 발견할 때마다 안쪽 루프의 상한 idcnt가 늘어난다 — "탐지된 장치를 다시 시작점으로" 쓰는 BFS형 확산이다. 모든 장치가 등장(idcnt == N)하는 순간 두 루프 모두 멈춰, 더 비싼 파워 단계로 넘어가지 않는다. Union(j, rid)의 인자가 재번호 인덱스(1..N)라는 점도 중요하다 — 거대한 원 ID 대신 작은 인덱스를 쓰므로 root[] 배열이 256칸으로 충분하다.
Find/Union은 경로 압축으로 거의 상수(α(N), 역아커만)다. 한 TC에서 scan_device 호출 수는 최악의 경우 6 × N + N(보정) — N ≤ 256이므로 ~2000회. 호출당 채점기 내부 계산은 O(N)의 장치쌍 순회. 따라서 한 TC의 알고리즘 비용은 O(N²) 수준으로 가볍다. 정작 무거운 것은 점수(시간이 아니라 power³ 누적)이며, §2·§4의 파워 전략이 그 점수를 CUT 21B 아래로 누른다. 30 TC 누적이 채점 대상이다.
점진 파워 루프가 끝나도 그룹핑이 완벽하지 않을 수 있다. 같은 방인데 두 개 이상의 그룹으로 갈라진 경우가 남는다 — 방이 길거나 ㄱ자 모양이라, 방 안의 한쪽 끝 장치와 다른 쪽 끝 장치 사이 거리가 약한 파워의 도달 범위를 넘었을 때다.
보정 단계는 파워 195로 각 그룹의 루트만 다시 스캔한다. 195는 powerList의 100과 300 사이에 있는 값이다 — 100으로는 못 닿았지만 300까지 안 올려도 되는 "중간 사거리"를 노린 휴리스틱이다. 비용도 195³ ≈ 7.4×10⁶으로 300³(2.7×10⁷)의 4분의 1, 같은 방 안의 멀리 떨어진 두 장치를 잇기에 충분하면서 300보다 싸다.
보정 루프는 if (i != root[i]) continue;로 각 그룹의 대표 장치(루트)만 재스캔한다. 두 그룹 G₁, G₂가 실제로 같은 방이라면, G₁의 어떤 장치든 G₂의 어떤 장치든 같은 방이다 — 따라서 G₁의 루트가 G₂의 루트(또는 멤버)를 195파워로 탐지하면 Union 한 번으로 두 그룹 전체가 합쳐진다(Theorem 1의 동치 폐포). 그룹 수는 장치 수보다 적으므로, 루트만 보는 것이 비싼 195 스캔의 호출 수를 줄이는 최적화다.
코드 주석이 "루트인 경우만 탐색하는 방법 : 반례검증이 필요!!!"라고 적은 것은 — 이 최적화가 "G₁ 루트와 G₂ 루트가 서로의 195 사거리 안에 있다"를 가정한다는 솔직한 경고다. seed=5 · 30 TC 데이터에서는 이 가정이 성립해 PASS가 검증됐다.
그룹핑이 끝나면 채점기 verify가 요구하는 형식 — mDeviceIds[방][장치] 행렬 — 으로 출력해야 한다. 채점기 verify는 user의 출력을 gDevice[i][j].id와 위치까지 정확히 비교하므로, 각 방 안의 장치들이 채점기가 부여한 순서(원 ID 오름차순)로 놓여야 한다.
void radixSort() { rnt *ap = ids, *bp = trr, *tp; rnt i, j; for (i = 0; i < 32; i += 8) { // 8비트씩 4패스 → 32비트 키 정렬 for (j = 0; j < DLM; ++j) cnt[j] = 0; for (j = 1; j <= N; ++j) cnt[(keys[ap[j]] >> i) & MASK]++; // 현재 바이트 빈도 for (j = 1; j < DLM; ++j) cnt[j] += cnt[j - 1]; // 누적합 for (j = N; j > 0; --j) bp[cnt[(keys[ap[j]] >> i) & MASK]--] = ap[j]; // 안정 배치 tp = ap, ap = bp, bp = tp; // 버퍼 스왑(핑퐁) }}
radixSort는 32비트 원 ID를 8비트씩 네 번 LSD(최하위 자리부터) 정렬한다 — 각 패스가 안정 정렬이므로 네 패스를 거치면 전체가 정렬된다. result()는 정렬된 ids[] 순서대로 장치를 훑으며 Find(ids[i])로 그룹 루트를 구하고, 그 루트가 처음 등장하면 새 행 번호 an++를 부여한다. 결과적으로 같은 방 장치들이 원 ID 오름차순으로 한 행에 모인다 — 채점기 verify의 위치별 비교를 통과하는 핵심이다. radix sort를 쓰는 이유는 ID가 32비트 정수라 비교 정렬보다 O(N)이 확실하기 때문이다.
getID 해시 체인은 거대 ID를 작은 인덱스로 압축, (2) Union-Find는 같은 방 관계의 동치 폐포 계산, (3) radix sort는 출력용 순서 복원. 각각 다른 자료구조가 다른 일을 맡고, 그 사이를 재번호 인덱스가 잇는다. 비싼 자원(파워³ 비용)은 §2·§3의 점진 전략에 집중하고, 싼 자원(시간)은 해시·radix에 자유롭게 쓴 설계다.
| 전략 | 정확성 | 점수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 모든 쌍을 파워 1000으로 | 보장 | CUT 초과 | 쉬움 | 호출당 10⁹ — 세제곱 비용이 점수를 폭발시킴 |
| 고정 중간 파워(예: 300) | 불완전 | 중간 | 쉬움 | 벽 너머 먼 장치를 못 잡아 그룹핑 오류 → PENALTY 위험 |
| 이분 탐색으로 최소 파워 | 보장 | 중간 | 복잡 | 장치쌍마다 탐색 → 스캔 호출 수 폭증, 누적 비용 큼 |
| 점진 파워 + Union-Find + 195 보정 | 보장 | CUT 통과 | 중간 | 약한 파워 우선 + 조기종료 + 갈라진 그룹 재결합 |
표가 드러내는 구조는 명확하다. 정확성(Theorem 1)은 "같은 방의 모든 쌍을 빠짐없이 발견"할 때만 보장된다 — 고정 중간 파워는 이 조건을 어겨 PENALTY 위험을 안는다. 진짜 경쟁은 세제곱 비용에서 벌어진다. 일괄 파워 1000은 정확하지만 호출당 10억으로 CUT을 넘고, 쌍별 이분 탐색은 최소 파워를 찾지만 스캔 호출 수 자체가 폭증해 누적 비용이 크다. 점진 파워는 — Theorem 2가 보장하듯 — 각 쌍을 최소 파워에서 처리하고 조기 종료로 비싼 단계를 건너뛰며, 195 보정으로 정확성의 마지막 구멍을 메운다. 이 조합만이 CUT 21B를 통과한다.
getRet == power만으로 같은 방을 판정하면, 파워가 1까지 닳은 경계 신호가 우연히 식을 만족해 다른 방을 같은 방으로 오판할 수 있다. detected.power > 1 가드가 이 오판을 막는다 — 빠뜨리면 PENALTY 10조.
idcnt < N이 없으면, 모든 장치가 이미 등장했는데도 파워 1000 단계까지 끝까지 돌아 — 불필요한 10억짜리 스캔이 누적된다. 조기 종료가 세제곱 비용 절감의 핵심.
if (i != root[i]) continue;를 빼면 같은 그룹의 모든 멤버를 195파워로 재스캔 — 호출 수가 그룹 수가 아니라 장치 수가 되어 비용이 수 배로 뛴다. 루트만 봐도 동치 폐포로 그룹 전체가 합쳐진다.
scan 진입 시 st[]를 0으로 초기화하지 않으면 이전 TC의 체인이 남아 ID 재번호가 어긋난다. root[i]=i, st[i]=0 초기화가 매 TC 필수 — 30 TC가 누적 채점되므로 한 TC만 어긋나도 전체 실패.
result는 정렬된 ids[]를 순회하며 그룹 루트가 처음 등장할 때만 새 행 번호를 준다. 정렬을 건너뛰거나 루트 판정을 Find 대신 root[] 직접 참조로 하면(경로 미압축) 같은 방이 두 행으로 갈라져 verify 실패.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력이다. main.cpp는 seed=5로 30개 TC를 돌리고, 각 TC마다 scan_device 비용(power³)을 gTotalCost에 누산한다. result로 받은 그룹핑을 verify가 원래 방 구성과 비교해 하나라도 틀리면 gTotalCost에 PENALTY 10조를 더한다.
g++ -O2로 main.cpp + user.cpp를 컴파일하고 input.txt(100×100 방 배치 맵)를 주면, 채점기가 seed=5로 30 TC를 돌려 SCORE와 판정을 출력한다. SCORE가 CUT 21,000,000,000 이하이면 PASS다. verify가 방 구성을 장치 단위로 정확히 대조하므로, PASS 판정은 곧 §2의 Union-Find 정확성 증명과 §4의 195 보정이 30개 TC 데이터 위에서 모두 성립함을 뜻한다.