§ 1문제 정의
드론은 한 번에 한 박스만 들고, 빈 손은 박스 위로 날 수 없으며(z < h), 든 손은 박스 옆으로 날 수 없다(z ≤ h). 매 동작은 비용 1.
세 단계 풀이: ① 모든 셀의 현재 높이를 한 번 훑어서 기록한다. ② 출발 셀의 박스를 우선순위(목적지의 행 짝/홀로 결정되는 ‘방문 순서’) 오름차순으로 재정렬한다. ③ 99,99에서 0,99까지 진행하며, 매 목적 셀마다 도착해야 하는 박스들을 무게 내림차순으로 다시 쌓는다.
핵심 기교: ‘직전 셀’을 임시 작업 공간으로 쓰면 한 스택을 뒤집어 다시 쌓을 수 있다. 두 스택 사이를 핑퐁하며 정렬 — O(N) 박스로 작동하는 일종의 selection sort.
드론은 손이 하나뿐이다 — 한 박스를 옮기려면 그 위 모든 박스를 먼저 들어내야 한다.
§ 2예제 시각화 — 한 셀의 4박스 스택 정렬
FIG. 9 — adjacent-cell ping-pong sort, side view
STEP 01 / 8
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
process():
myInit()
getHeight() # 모든 셀의 현재 높이
getInfoAndArrange() # 각 출발 셀의 박스를 prior 순으로 재정렬
destSort() # 목적지별 무게 내림차순 목록 준비
for (r, c) along snake (0,99) → (99,99):
mymove(drone, r, c, 0) # 빈 손으로 이동
build(prev_cell, B[r][c].stk) # prev 셀을 임시 공간으로 정렬해 쌓기