[Python] 하노이 탑 경로, 이동 횟수 구하기

하노이 탑의 경로와 이동 횟수를 알기 위해선 시작점과 끝점 뿐만 아니라 어디를 거쳐서 이동하는지도 고려해야한다. n번 원판이 가장 아래 있기 때문에 이 원판을 옮기기 위해선 그 위에 있는 n-1개의 원판을 다른 곳으로 이동 시켜야 한다.

• 시작 : a(파이썬에서 from 이미 모듈을 가져오는데 사용되므로 a로 변수명을 정하였다.)
• 거쳐가는 곳 : by
• 끝: to

알고리즘은 다음과 같다.

1. n-1개의 원판을 by에 옮긴다.
2. n번째 원판을 to로 옮긴다.
3. by에 있는 n-1개의 원판을 to로 옮긴다.

이 알고리즘을 바탕으로 다음과 같이 코드를 작성해 볼 수 있다.

def hanoi (a ,by,to,n):
  if n==1:
    print("1: "+a+" --> "+to)
    return 1
  ans=0
  ans+=hanoi(a,to,by,n-1)
  ans+=1
  print(str(n)+": "+a + " --> "+ to)
  ans+=hanoi(by,a,to,n-1)
  return ans

print(hanoi("1","2","3",3))