하노이의 탑

자꾸 미노이의 탑이라고 속삭이는 날 발견..ㅈㅅ

하노이의 탑

n개의 원반을 target 지점으로 최소 횟수로 옮기기
단, 아래의 원칙을 지키면서

• 가장 큰 원반 -> 작은 원반 순으로 쌓기

가정) 1번이 출발 지점, 3번이 목표 지점, 2번이 경유 지점

main concept

정리하자면,
1. N-1개의 원반을 경유지로 옮긴다
2. N번 원반을 도착지로 옮긴다
3. N-1개의 원반을 도착지로 옮긴다

이를 구현하는 건 그대로 코드로 옮기면 된다

구현

def hanoi(n, src, target, tmp):
    if n == 1:
        print(f"{n}: {src} to {target}") #1을 옮김
        return
    
    hanoi(n-1, src, tmp, target) #원반 n-1개를 경유지로 옮김
    print(f"{n}: {src} to {target}") #n을 옮김
    hanoi(n-1, tmp, target, src)
    
    return

재귀함수를 짤 땐 종료조건을 유의해서 짜야 하는데,
여기서 종료조건은 원반이 1일 때, 그대로 옮기면 되므로 n이 1일 때이다.