1914. 하노이 탑

옛날에 하노이 탑을 직접 해봐서 규칙이 있다는 것을 알았다. 하지만 코드로 구현하는데 어려움을 겪었다.

재귀 호출을 통해 구현할 수 있는데 재귀함수 하나를 정의해야한다.

f(n,a,b,c) → n개의 원판이 a기둥에 있을 때, c기둥으로 모두 이동 시키는 함수

1. n-1개의 원판을 2번기둥으로 옮김
2. 1번 기둥에 남아있는 한개의 원판을 3번으로
3. 2번기둥에 있는 n-1개의 원판을 3번 기둥으로

def f(n, a, b, c):
  if(n == 1):
    print(a, c, sep = " ")
  else:
    f(n-1, a, c, b)
    f(1, a, b, c)
    f(n-1, b, a, c)

n = int(input())
print(2**n-1)
if(n <= 20):
  f(n, 1, 2, 3)

위 코드로 하노이탑의 순서를 나타낼 수 있다.