하노이 문제는 기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때,

아래의 규칙에 따라 1번 기둥에 있는 모든 원판을 3번 기둥으로 이동하는 문제이다.

규칙1) 한 번에 하나의 원판만 이동시킨다.

규칙2) 작은 원판위에 큰 원판을 놓을 수 없다.

위 규칙대로 하노이 탑 완구를 가지고 문제를 풀던 수민이는 너무 지겨워서 새 규칙을 만들었다.

규칙3) 원판은 항상 인접한 오른쪽 기둥으로만 이동 가능하다.

만약 오른쪽 기둥이 없을 경우 가장 왼쪽 기둥으로 이동한다. 1->2, 2->3, 3->1

수민이는 당신에게 하노이 탑의 상태를 보여주며 이 상태가 올바른 상태인지 물어보았다.

올바른 상태란, 위 규칙대로 최소 이동 횟수로 하노이 탑 문제를 해결하는 과정에서 나오는 상태를 말한다.

예를 들어, 원판이 3개가 있을 때, 아래 그림은 올바르지 않은 상태다.

현재 원판들의 위치 상태가 주어졌을 때 수민이의 하노이 탑이 올바른 상태인지 알려주자.

하노이 탑 검증하기 2 timer 1s memory 128MB

하노이 탑 검증하기 2 1s 128MB