하노이의 탑

### 하노이의 탑 ###

: 3개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있다.

​

: n개의 원판 일 경우 원판을 모두 마지막 기둥으로 옮길 수 있는 방법의 수는 (2^n) - 1번 이다 (메르센 수)

​

​

< 조건 >

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있으면 안된다.

 

출처:https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

 

# 첫 번째 규칙 1->2, 1->3, 2->3을 잘 생각해서 재귀 하면 된다.
# 재귀할 때 해당 code 다 끝나면 돌아온다.

def hanoi(n, from_, to_, by_):
    if n == 1:
        print(from_, by_)
    else:
        hanoi(n-1, from_, by_, to_)
        print(from_, by_)
        hanoi(n-1, to_, from_, by_)