하노이 타워 이동 순서

문제

기둥 세 개와 크기가 모두 다른 원판 $h$개가 있다. 원판은 전부 출발 기둥에 크기 순으로 쌓여 있다. 한 번에 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 놓을 수 없다.

원판 $h$개를 출발 기둥에서 도착 기둥으로 옮기는 순서는 세 단계로 나뉜다. 위의 $h-1$개를 중간 기둥으로 옮기고, 맨 아래 원판 하나를 도착 기둥으로 옮기고, 중간 기둥에 있던 $h-1$개를 도착 기둥으로 옮긴다. 첫 단계와 마지막 단계는 기둥의 자리만 바꾼 같은 문제이므로 재귀 호출로 처리한다.