Hanoi Tower

http://211.228.163.31/30stair/hanoi1/hanoi1.php?pname=hanoi1 

문제를 요약하자면 현재상태의 하노이 탑이 주어졌을때 1,2,3번 기둥중 어떤기둥으로 옮기는지는 상관없고, 최소의 이동으로 모든 조각을 한곳에 모을때 최소이동과 어디로 모으는 것이 최적인지 구하는것이다.

 
일단 이문제는 linear 하게 풀릴수 있다.
가장 쉽게 떠올릴수 있는 방법이 모든 경우를 다해보는 backtracking 기법인데. 
이문제의 실제 N범위가 100,000인걸 감안한다면 으론 해결할수 없다.

그렇다면 어떻게  접근해야 풀수 있을까?

1)
우선  우리는 N개의 하노이를 한 기둥에서 다른기둥으로 옮기기 위해 이동해야하는 최소횟수는  임이 자명하다.

2)
그리고 우리가 최종적으로 옮겨야할 목적지는 가장 큰 조각이 위치한 기둥임을 직관적으로 알수 있을것이다. 

이유를 설명하자면 가장큰 조각이 존재하는 기둥을 P1이라고 한고 P2에 모든 조각을 모은다고 하자.
P2에는 어떠한 조각이 있더라도 가장 큰 조각이 P2의 가장 밑바닥에 깔려야 함으로 이는 P2의 모든조각을 P3으로 옮긴뒤 P1에 존재하는 가장 큰 조각을 P2 로 옮겨야된다.  그러나 생각해보면 맨처음 상태나 위와같이 가장큰 조각을 P2로 옮긴 뒤 상태나 기둥의 번호만 바뀔뿐 다른 것은 바뀐것이없다. 즉 필요없는 이동만 늘어난 샘이 된것이다.

위 두 힌트를 잘 사용한다면  솔루션을 만들어 낼수 있고,

에서 한줄만 바꾸면(주석처리만 하면)  솔루션을 얻어 낼수 있을것이다.