백준 11729풀이와 해설 - 하노이탑 쌓기

def cnt(N):     #몇번 옮기는지 세어주는 함수
    N_time=1
    for i in range(1,N):
        N_time=N_time*2+1     
    print(N_time)

def move(N,start,fin):  #어떤 순서로 탑에서 탑으로 이동하는지 나타내주는 함수
   
    wait= list({1,2,3}-{start}-{fin})[0]    #1,2,3중에 start와 fin빼고 남는거    
   
    if N>=2:
         move(N-1,start,wait)
         print("{0} {1}".format(start,fin))
         move(N-1,wait,fin)
    if N==1:
        print("{0} {1}".format(start,fin))



disk_num=int(input())

cnt(disk_num)           #몇번 움직이는지  먼저 출력
move(disk_num,1,3)      #움직이는 과정 출력

 

문제의 key idea는 move함수에서 볼 수 있듯

 

N개의 원판을 1번에서 3번 탑으로 옮기는 과정에서는

 

일단 가장 큰 N번째 원판을 1번에서 3번으로 꺼내기 위해서는

 

2번 탑에 N-1 높이 탑을 쌓아서 (move(N-1)함수를 1번에서 2번으로 시행하도록 설정)

 

1번에서 N짜리 큰 원판만 남겨두고 N원판을 1->3으로 옮긴 후 

 

가장 큰 N원판을 3번 탑에 깐 채로 그 위에 N-1높이의 탑을 쌓으면 완성! 이라는 점.

 

 

정리하면,

 

2번 탑에 N-1짜리 높이의 탑 쌓기(move(N-1,start,wait)) ->

 

1번 탑에 하나 남은 N짜리 큰 원판을 3번에 옮기기 () ->print("{0} {1}".format(start,fin)) 로 대충 처리

 

2번탑에 있는 N-1 높이 탑을 3으로 옮기기 (move(N-1,wait,fin))