[알고리즘] 하노이의 탑

n = int(input()) # 정수 입력받기    

def hanoi_tower(n, fr, tmp, to): #함수 정의 ,n개의 원판을 fr에서 출발하여 tmp를 거쳐 to로 이동시키는 과정을 수행
    if n == 1:  # n=1일 때
        print("원판 1: %s --> %s" % (fr, to)) #첫번째에서 세번째로 바로 이동시킴
    else:   
        # n이 1이 아닐 때 fr에서 tmp로 이동시키고, 
        # 가장 큰 원판을 fr에서 to로 이동시킨 후, 
        # 다시 tmp에서 to로 n-1개의 원판을 이동시킵니다. 
        hanoi_tower(n-1, fr, to, tmp) # 
        print("원판 %d: %s --> %s" % (n, fr, to))
        hanoi_tower(n-1, tmp, fr, to)

hanoi_tower(n, 'A', 'B', 'C')

 

복잡도 O(2^n)