이 페이지는 "왜 이 풀이가 통과하는가"를 끝까지 따진다. 그리디 보행이 멈추는 지점에서 다익스트라가 최단경로로 잇는다는 결합의 정당성, 회전 4벌 매칭이 SCAN을 거의 0으로 만드는 정보이론적 이유, 그리고 SCORE 4,801,170을 만든 실제 C++ 구현 전체를 라인 단위로 해부한다.
로봇청소기 문제의 채점 점수는 SCAN·20 + MOVE·10 + TURN·15의 총합이다. 모든 칸을 방문하는 것은 필수 제약이고, 점수는 "얼마나 적은 호출로 그것을 해냈는가"로 매겨진다. 따라서 베스트 해법은 두 개의 독립된 최적화 문제로 분해된다.
핵심 통찰은 이 둘이 충돌하지 않는다는 것이다. 이동 전략은 맵 정보가 주어졌다고 가정하고 짤 수 있고, 정보 전략은 이동과 독립적으로 "언제 SCAN을 생략해도 되는가"만 판정하면 된다. 풀이는 정확히 이 분해를 따른다.
로봇은 매 칸에서 그리디하게 행동한다 — 인접한 미청소 칸이 있으면 그곳으로 한 칸 전진한다. 그리디가 막히는 순간(사방이 벽이거나 이미 청소됨)에만 다익스트라를 호출해, 가장 가까운 미청소 칸까지의 최소비용 경로로 점프한다. 그리디는 호출당 O(1)로 싸지만 막다른 골목에 갇히고, 다익스트라는 비싸지만 전역 최적 경로를 보장한다. 둘의 결합은 "싼 수단을 우선 쓰되, 그것이 실패할 때만 비싼 수단으로 보강"하는 전형적인 하이브리드다.
10개의 sub-task는 모두 같은 집에서 진행되며, 로봇만 매번 랜덤한 위치·방향으로 떨어진다. 그러므로 SCAN으로 맵을 알아낼 필요는 딱 한 번뿐이다. 첫 sub-task에서 전체 맵을 구축해 4방향 회전본으로 저장하고, 2번째 sub-task부터는 작은 단서(몇 칸의 SCAN)만으로 "현재 집이 4개 회전본 중 어느 것인지 + 로봇이 어디에 있는지"를 특정한다. 그 시점부터 SCAN은 완전히 꺼진다.
먼저 가장 약한 보장부터 확인한다: 이 전략은 반드시 모든 칸을 청소하는가? 점수보다 우선, 미청소 칸이 하나라도 남으면 PENALTY 10억이 부과되어 즉시 실패한다.
매 루프 반복 후 다음이 성립한다: 로봇은 청소된 칸 위에 있고, findPos()가 0을 반환했을 때에만 루프가 끝난다.
그리고 findPos()가 0을 반환한다는 것은 — 다익스트라가 시작 칸에서 도달 가능한 모든 칸을 탐색했음에도 미청소 칸을 하나도 찾지 못했다는 뜻이다.
집의 빈 칸들이 4방향 인접으로 모두 연결되어 있다면(채점 데이터는 항상 그렇다), 그리디+다익스트라 보행은 모든 빈 칸을 청소한 뒤에만 종료한다.
루프가 종료되었다고 하자. 종료는 오직 findPos()==0으로만 일어난다(§3의 코드 라인 95 참조). findPos()는 로봇의 현재 칸을 시작점으로 다익스트라를 수행하며, 벽이 아니고 아직 정보가 없는(값 3) 칸을 제외한 모든 칸으로 간선을 확장한다.
반환값 0은 우선순위 큐가 빌 때까지 Map[t.r][t.c]==0(미청소 빈 칸)인 노드를 한 번도 만나지 못했음을 의미한다. 큐는 시작 칸에서 도달 가능한 모든 칸을 방문하므로(다익스트라의 완전성), 도달 가능 영역 안에 미청소 칸이 없다.
빈 칸 전체가 연결되어 있다는 가정에서, 로봇이 서 있는 청소된 칸으로부터 모든 빈 칸이 도달 가능하다. 따라서 "도달 가능 영역에 미청소 칸 없음"은 곧 "미청소 칸 없음"이다.
그리디는 "탐욕적"이라는 이름 때문에 종종 최적성을 의심받는다. 그러나 여기서 그리디의 역할은 경로 길이의 하한을 건드리지 않는다. 핵심은 다음 보조정리다.
현재 칸에 인접한 미청소 칸이 존재한다면, 그 칸으로 한 칸 전진하는 것은 어떤 최적 보행에도 포함될 수 있는 수다.
이유: 인접 미청소 칸 c는 언젠가 반드시 방문해야 한다. 지금 방문하든 나중에 방문하든 c에 "들어가는" MOVE 1회는 불가피하다. 지금 바로 전진하면 추가 비용 없이(이미 인접) 그 불가피한 MOVE를 소비하는 것이고, 미루면 나중에 c 근처로 되돌아오는 경로 비용이 더해진다. 따라서 즉시 전진은 결코 손해가 아니다.
그리디가 막히는 지점 — 인접 미청소 칸이 없을 때 — 에서만 "어디로 점프할 것인가"라는 진짜 선택이 생긴다. 이때 다익스트라는 가장 가까운 미청소 칸을 고른다. 이는 최근접 이웃(Nearest-Neighbor) 휴리스틱으로, 일반 TSP에서는 최적이 아니지만, 격자에서 "막힌 지점 → 가장 가까운 미탐색 영역"이라는 국소 결정은 거의 항상 좋은 선택이며 구현이 단순하다. 다익스트라의 비용 함수가 MOVE·10에 더해 방향 전환을 TURN·15로 정확히 반영(코드 라인 73의 !!rd * 15)하기 때문에, 회전이 잦은 우회로보다 직선 경로를 선호한다.
이 문제의 다익스트라는 교과서 버전과 한 가지가 다르다. 노드가 격자 칸 (r, c)가 아니라 칸과 방향의 쌍 (r, c, dir)이다. 방향을 상태에 넣는 이유는 TURN 비용 때문이다 — 같은 칸이라도 어느 방향을 보고 도착했는지에 따라 다음 회전 비용이 달라진다.
[d ≠ nd]는 아이버슨 괄호 — 방향이 바뀌면 1, 아니면 0이다. 코드에서는 상대 회전량 rd에 대해 !!rd * 15로 표현된다. rd가 0이면 회전 없음(0점), 1·2·3이면 회전(15점)이다. 비용이 음수가 아니므로 다익스트라의 전제(음의 간선 없음)가 성립하고, 따라서 우선순위 큐에서 처음 꺼낸 노드의 거리는 확정 최단거리다.
아래는 실제 통과 코드의 다익스트라 부분(findPos)이다. SCORE 4,801,170을 만든 구현 그대로다.
int findPos() { fr = 0; ++vcnt; // 방문표식 세대 번호 갱신(메모리 0초기화 회피) pq.clear(); pq.push({ row, col, dir, 0, 0, 0 }); // 시작 상태: 거리 0 while (!pq.empty()) { t = pq.top(); pq.pop(); if (visited[t.r][t.c][t.ad] == vcnt) continue; // 이미 확정된 상태 스킵 visited[t.r][t.c][t.ad] = vcnt; que[++fr] = t; // 경로 역추적용 백업 if (Map[t.r][t.c] == 0) break; // 미청소 빈 칸 도달 → 목표 발견 for (int rd = 0; rd < 4; ++rd) { int nd = (t.ad + rd) % 4; int nr = t.r + dr[nd], nc = t.c + dc[nd]; if (visited[nr][nc][nd] == vcnt || Map[nr][nc] == 1 || Map[nr][nc] == 3) continue; pq.push({ nr, nc, nd, rd, fr, t.cost + 10 + !!rd * 15 }); } } if (Map[t.r][t.c]) return 0; // 미청소 칸을 못 찾음 → 청소 완료 // 역추적: 백업 큐를 따라 상대 방향열을 복원 for (int i = fr; i > 1; i = que[i].path) entry[++ecnt] = que[i].rd; for (; ecnt > 0; --ecnt) { // 역순 저장 → 정순 실행 int d = entry[ecnt]; if (d) turn(d); move(); } row = t.r, col = t.c, dir = t.ad; return 1;}
visited를 매번 0으로 초기화하지 않고 세대 번호 vcnt로 비교하는 트릭에 주목하라. 64×64×4 = 16,384개 원소를 sub-task마다 memset하면 누적 비용이 크다. ++vcnt 한 줄로 "이전 세대의 모든 표식을 무효화"하는 것이 O(1)이다. 우선순위 큐에 같은 상태가 여러 번 들어갈 수 있으므로(거리 갱신 대신 재삽입), 라인 9의 중복 스킵이 정확성을 지킨다.
findPos() 1회 호출의 시간 복잡도는 O(V log V)이며, V = 64·64·4 ≈ 1.6×10⁴다. 각 상태는 최대 4개의 간선을 가지므로 큐에 들어가는 항목은 O(4V), 이진 힙 연산이 O(log V)이므로 호출당 약 6.5×10⁴ · 14 ≈ 9×10⁵ 연산. 보행 전체에서 findPos가 호출되는 횟수는 막다른 골목 수에 비례하며 수십 회를 넘지 않으므로, sub-task당 다익스트라 총비용은 ~10⁷ — 충분히 빠르다.
점수에서 SCAN은 1회 20점으로 가장 비싸다. 순진하게 매 칸 SCAN하면 4096칸 × 20 = 81,920점이 SCAN에만 쓰이고, 그것이 10 sub-task 누적되면 SCAN만으로 80만 점을 넘는다. 베스트 해법은 이 비용의 대부분을 회전 매칭으로 제거한다.
process1()은 그리디+다익스트라 보행으로 집 전체를 돌며, "현재 방향으로 3칸 이동 후 1회 SCAN"의 리듬으로 맵을 채운다(fwCnt > 2 조건). 3×3 SCAN이 3칸 전진마다 겹치며 들어오므로 빈틈없이 맵이 복원된다. 보행이 끝나면 복원된 64×64 맵을 0°·90°·180°·270° 회전본 4벌로 info[0..3]에 저장한다.
for (i = 0; i < 64; ++i) { for (j = 0; j < 64; ++j) { info[0][i][j] = Map[sr+i][sc+j] != 2; // 0° (벽=1, 빈칸=0) info[1][63-j][i] = info[0][i][j]; // 90° 회전 info[2][63-i][63-j] = info[0][i][j]; // 180° 회전 info[3][j][63-i] = info[0][i][j]; // 270° 회전 }}
2번째 sub-task부터 로봇은 맵을 모르는 척 다시 보행을 시작하되, 몇 칸만 SCAN해 작은 부분 맵 조각을 모은다. searchMap()은 이 조각을 4개 회전본 각각에 대해 모든 위치에 슬라이딩하며 일치하는 곳을 찾는다.
searchMap()이 4개 회전본 × 모든 위치를 통틀어 정확히 한 곳에서만 부분 맵과 일치한다면, 그 순간 로봇의 절대 위치·방향·집 모양이 확정된다. 이후 SCAN은 완전히 불필요하다.
부분 맵 조각의 모든 알려진 칸이 어떤 회전본의 어떤 위치에 정확히 겹친다면, 그 (회전, 위치) 쌍은 "현재 관측과 모순 없는 가설"이다. 코드 라인의 if (ansR > -1) return 0;은 그런 가설이 둘 이상 발견되는 즉시 실패(아직 특정 불가)를 반환한다. 따라서 함수가 1을 반환했다면 모순 없는 가설은 유일하다.
가설이 유일하다는 것은 곧, 남은 미관측 칸의 값도 그 회전본으로부터 유일하게 결정된다는 뜻이다(다른 가설이 없으므로 반례가 존재할 수 없다). 그러므로 나머지 맵을 회전본에서 그대로 복사해도 실제 집과 일치한다. SCAN 없이 보행을 마쳐도 완전 청소가 보장된다.
loop > 10 조건(라인: 충분한 칸을 본 뒤)에서만 searchMap()을 호출하고, 유일성(ansR > -1 재발견 시 실패)을 엄격히 요구하는 것은 이 함정을 막기 위한 이중 안전장치다.
정보이론의 언어로 말하면: 첫 sub-task의 SCAN은 집의 엔트로피 H(map) 전부를 사들이는 1회성 투자다. 2번째부터 남은 불확실성은 "4개 회전 중 무엇 + 위치 (Δr, Δc)" 뿐이며, 이는 log₂4 + log₂(64²) ≈ 2 + 12 = 14비트에 불과하다. 14비트는 SCAN 몇 번이면 충분히 분해되는 작은 양이고, 그래서 2번째 이후 sub-task의 SCAN 비용이 거의 0으로 수렴한다.
| 전략 | 완전성 | 점수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 순수 그리디 (DFS) | 보장 | 높음 | 쉬움 | 막다른 골목 복귀가 지그재그 → MOVE 폭증 |
| 매 칸 SCAN + 그리디 | 보장 | CUT 초과 | 쉬움 | SCAN 81,920점/sub-task — 회전 재사용 없이는 탈락 |
| 전역 TSP 최적 경로 | 보장 | 최소 | 불가 | 4096칸 TSP는 NP-난해 — 시간 안에 못 풂 |
| 그리디 + 다익스트라 + 회전 캐시 | 보장 | 4,801,170 | 중간 | 싼 그리디 + 드문 다익스트라 + 1회성 SCAN 투자 |
표가 보여주는 구조는 명확하다. 완전성은 그리디 계열이면 거의 공짜로 얻는다(Theorem 1). 진짜 경쟁은 점수에서 벌어지며, 두 개의 비용원 — 막다른 골목 복귀(MOVE)와 정보 획득(SCAN) — 을 각각 다익스트라와 회전 캐시로 공략한 조합만이 CUT을 넉넉히 통과한다. 전역 TSP는 이론적 최소를 주지만 시간 제약 안에서 불가능하므로, "다익스트라 NN 점프"가 현실적 최선이다.
visited == vcnt 검사로 오래된 항목을 반드시 버려야 한다. 이 검사가 빠지면 거리가 틀린다.
vcnt 트릭은 호출 횟수가 int 범위를 넘지 않는다는 전제다. 이 문제 규모(sub-task당 수십 회 × 10 sub-task × 10 TC)에서는 안전하지만, 더 큰 문제로 이식할 때는 주기적 memset 폴백이 필요하다.
(i,j)↦(63−j,i)를 작은 예제(예: 2×2)로 손검증하라.
loop > 10 같은 "충분히 본 뒤" 가드를 두어라.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력이다.
main.cpp는 seed = 5 고정에 10 TC를 돌린다. g++ -O2로 main.cpp + user.cpp를 함께 컴파일하고 64×64 맵 입력을 주면 SCORE: 4801170 과 PASS가 출력된다. 채점기가 점수를 직접 누산하므로(SCAN/MOVE/TURN 호출 시점에 가산), 이 숫자는 곧 풀이의 객관적 성적표다.