8.6 하노이타워

문제 

전형적인 하노이타워에서는 크기가 서로 다른 N개의 원반을 세개의 기둥 중 아무 곳이나 옮길 수 있다. 초기에 원반의 크기가 맨 위에서부터 아래로 커지는 순서대로 쌓여있다. 그리고 문제에는 다음과 같은 제약 조건이 있다.

1. 원반을 한번에 하나만 옮길 수있다.

2. 맨 위에 있는 원반 하나를 다른 기둥으로 옮길 수 있다.

3. 원반은 자신보다 크기가 작은 디스크 위에 놓을 수 없다 .

 

스택을 사용하여 모든 원반을 첫번째 기둥에서 마지막 기둥으로 옮기는 프로그램을 작성하라 .

 

해결법

n=1 

 1. 원판1을 기둥1에서 기둥3으로 옮긴다

n=2

 1. 원판1을 기둥 1에서 기둥 2로 옮긴다.

 2. 원판2을 기둥 1에서 기둥 3로 옮긴다.

 3. 원판 1을 기둥 2에서 기둥 3로 옮긴다.

n=3

 1. 원판1을 기둥 1에서 기둥3으로 옮긴다.

 2. 원판2를 기둥 1에서 기둥 2로 옮긴다.

 3.원판 1을 기둥 3에서 기둥 2로 옮긴다.

 4. 원판3을 기둥 1에서 기둥3으로 옮긴다.

 5. 원판1을 기둥 2에서 기둥 1으로 옮긴다.

 6. 원판2를 기둥 2에서 기둥 3으로 옮긴다.

 7. 원판1을 기둥 1에서 기둥 3으로 옮긴다.

 

결국 기둥의 번호는 그렇게 중요하지 않다. 기둥 2를 버퍼로 사용해서 원판을 3으로 옮기는 것과 기둥 3을 버퍼로 사용해서 원판을 기둥 2로 옮기는 것은 똑같은 작업이다. 

def moveDisk(n ,origin, destination, buffer):
    if n<=0:
        return
    moveDisk(n-1, origin,buffer, destination)
    moveDisk(origin,destination)
    moveDisk(n-1, buffer,destination,origin)