하노이의 탑

하노이의 탑은 재귀로 풀 수 있는 가장 유명한 예제 중의 하나이다. 일반적으로 원판이 n개 일 때, 2^n-1번의 이동으로 원판을 모두 옮길 수 있다.

하노이의 탑에는 3개의 기둥이 존재한다. 첫번째 기둥은 원판이 처음 위치하는 출발지 기둥이고 2번째 기둥은 경유를 위한 기둥이며 3번째 기둥은 목적지 기둥이다.

n = 1일 때

• 1번 원판을 목적지로 옮긴다.

n = 2일 때

• 1번 원판을 경유지로 옮긴다.
• 2번 원판을 목적지로 옮긴다.
• 1번 원판을 목적지로 옮긴다.

n = 3일 때

• 1번 원판을 목적지로 옮긴다.
• 2번 원판을 경유지로 옮긴다.
• 1번 원판을 경유지로 옮긴다.
• 3번 원판을 목적지로 옮긴다.
• 1번 원판을 출발지로 옮긴다.
• 2번 원판을 목적지로 옮긴다.
• 1번 원판을 목적지로 옮긴다.

n = n개 일때

• N - 1 개의 원판을 경유지로 옮긴다.
• N번 원판을 목적지로 옮긴다.
• N - 1 개의 원판을 목적지로 옮긴다.
• 만약 1개면 바로 옮긴다

def hanoi(n, from_, to_, via_):
    if n == 1: # 원판이 한 개라면 바로 옮긴다.
        print(from_, '->', to_)
        return
    hanoi(n - 1, from_, via_, to_) # n-1개를 출발지에서 경유지로 옮긴다.
    print(from_, '->', to_)
    hanoi(n - 1, via_, to_, from_) # n-1개를 경유지에서 목적지로 옮긴다.
  

hanoi(3, 1, 3, 2)