재귀_하노이의 탑 알고리즘

hanoi(N, start, to, via): start에서 to로 via를 거쳐 총 N개의 원반을 운반할 때

 

• hanoi(3, ‘A’, ‘C’, ‘B’): 3개의 원반을 A에서 C로 B를 거쳐 옮기는 과정
  • hanoi(2,'A,',B','C'): 우선 두개의 원반을 B로 옮겨놓고 3번 원반을 C로 옮겨야함
  • hanoi(2, ‘B’, ‘C’, ‘A’): 3번 원반을 C로 옮긴 후 B에 있는 2개의 원반을 C로 옮김

 

N개의 원반을 옮기려면 N-1개의 원반을 B로 옮겨놓고 N번째 원반을 C로 옮긴 다음 N-1개의 원반을 B에서 C로 다시 옮겨야함

 

 

해당 알고리즘을 토대로 코드를 작성해보면

def move(n,start,to):
	print("{}에서 {}로 이동".format(n,start,to))
    
def hanoi(n,start,to,via):
	if n==1:
    	move(1,start,to)
    else:
    	hanoi(n-1,start,via,to)
        move(n,start,to)
        hanoi(n-1,via,to,start)

 

 

프로그래머스 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

def solution(n):
    answer = []
    def move(n,start,to):
        answer.append([start,to])
    
    def hanoi(n,start,to,via):
        if n==1:
            move(1,start,to)
        else:
            hanoi(n-1,start,via,to)
            move(n,start,to)
            hanoi(n-1,via,to,start)
    
    hanoi(n,1,3,2)
    
    return answer