§ 1문제 정의
로봇청소기는 자신의 위치도, 집의 모양도 모른다. 알 수 있는 건 발 밑 3×3의 상태뿐이다. 모든 청소되지 않은 칸을 방문하라 — 그게 cleanHouse() 한 번의 임무다.
매 sub-task마다 로봇은 집 어딘가에 랜덤하게 떨어진다. scan()으로 주변을 읽고, turn()으로 회전하고, move()로 한 칸 전진할 수 있다. 모두 점수에 가산된다.
핵심 아이디어는 두 가지다. 그리디 — 앞이 청소되지 않았다면 그냥 전진한다. 다익스트라 — 사방이 막혔다면 최단경로로 가장 가까운 미청소 칸으로 이동한다. 그 두 번째 sub-task부터는 첫 sub-task에서 얻은 맵을 회전·재사용하여 SCAN 호출을 거의 모두 절약한다.
SCAN은 비싸다. 두 번째 집은 첫 번째 집의 회전된 사본이다 — 정보를 다시 사지 마라.
§ 2예제 시각화 — 64×64를 16×16으로 압축
아래는 16×16 축소본. 짙은 칸은 벽, 흐린 칸은 청소 대상. 붉은 경로가 로봇의 이동, ◆는 SCAN 위치. 그리디로 막히면 다익스트라가 점프 경로를 만든다.
FIG. 1 — coverage walk on a 16×16 reduction
STEP 01 / 8
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
init():
taskCnt = 0
cleanHouse():
if first sub-task:
process1() # 전체 맵을 구축. SCAN을 4번에 1회 호출
save 4 rotations of Map into info[0..3]
return
# 2nd+ : 작은 단서로 회전·위치 추정 → SCAN 거의 없음
while there's an unvisited cell:
if forward is empty:
move()
else:
for d in [left, back, right]:
if (row+dr[d], col+dc[d]) is empty:
turn(d); move()
break
else:
findPos() # Dijkstra → nearest unvisited
if needScan and 10 moves passed:
searchMap() # 회전+위치를 결정짓는 지점