[Python][프로그래머스][Level3] 하노이 탑

[Python][프로그래머스][Level3] 하노이 탑

코드

answer=[]
def hanoi(x,y,z,num):
    if num==1:
        answer.append([x,y])
        return
    
    hanoi(x,z,y,num-1)
    hanoi(x,y,z,1)
    hanoi(z,y,x,num-1)
    
def solution(n):
    hanoi(1,3,2,n)
    return answer

재귀 문제로 유명한 하노이탑이다.

1의 위치에서 N개가 3으로 가는 방법은 N-1개를 2번에 옮기고 N번째 판을 3번으로 옮기고 N-1개를 다시 3번으로 옮기는 것이다.

N-1개를 2번으로 옮기는 방법도 N-2개를 3으로 옮긴 후 N-1번째 판을 2번으로 옮기고 N-2개를 다시 2번으로 옮긴다.

이 과정을 반복하는 것이다.

단, 1개일 경우 중간에 거치는 것 없이 바로 이동하면 된다.