[백준] 1914 하노이탑

https://www.acmicpc.net/problem/1914

 

하노이탑 규칙

1. 한 번에 하나의 원반만 이동할 수 있다.
2. 큰 원반이 작은 원반 위에 올려져서는 안 된다.
3. 원반은 항상 세 개의 막대 중 하나에 있어야 한다.

---

하노이탑 알고리즘의 동작 원리는 다음과 같다.

 

n-1개의 원판을 1번에서 2번 막대로 옮긴다
2. n번째 원판을 3번 막대로 옮긴다
3. n-1개의 원판을 2번에서 3번 막대로 옮긴다

이는 크게 세 가지의 동작
"n-1개를 start(시작막대)에서 6-start-end(보조막대) 로 옮기고" 
"남은 1개를 start(시작막대)에서 end(도착막대)로 옮기고" 
"n-1개를 6-start-end(보조막대) 에서 end(도착막대)로 옮기는" 것

으로 나눌 수 있다. 재귀를 사용하여  N개의 원반 문제를 n-1개의 원반 문제로 쪼개면서 해결한다.

 

한 번에 하나의 원반을 옮길 수 있는데, n-1개의 원반으로 계산하는 이유

마지막에 호출된 함수부터 return 되기 때문이라고 생각했는데, 재귀 문제의 핵심은 재귀적으로 반복하며 점점 작은 문제로 나누어 해결하는 것 이라고한다.

 

핵심 동작 원리

1. 큰 문제를 작은 문제로 쪼개기:
   • n개의 원반을 옮기는 문제를 n-1개의 원반을 옮기는 문제로 나눈다.
   • 이것은 하노이탑 문제의 재귀적 특성 때문입니다. n개의 원반을 옮기려면, 먼저 n-1개의 원반을 다른 막대로 옮겨야 큰 원반을 움직일 공간을 확보할 수 있기 때문에 이 방식이 자연스럽게 동작한다.
2. 가장 작은 단위까지 쪼개기:
   • 이 과정을 재귀적으로 반복하면, 결국 n=1일 때 문제를 해결할 수 있다. 즉, 원반이 1개 남으면 더 이상 쪼갤 수 없으므로 직접 원반을 옮긴다.
   • 이후, 재귀적으로 쪼개진 문제들이 해결되면서 다시 상위 문제로 올라가게 된다.

 

즉 재귀 호출은 마지막에 호출된 것이 먼저 끝나고, 그 상위 호출로 돌아가며 문제를 해결하게 되는데, 이 과정에서 큰 원반을 옮기기 위해 작은 원반들을 먼저 옮기는 순서가 유지되는 것이다.

 

Sol

def hanoi(n, start, end) : #n개 , 시작막대, 도착막대
    if(n == 1) : 
        print(start, end)
        return
    
    hanoi(n-1, start, 6-start-end) 
    #start,end 는 알지만 나머지 막대의 번호를 알 수 없으므로 (1+2+3)에서 start와 end를 뺀다
    print(start, end)
    hanoi(n-1, 6-start-end, end)
n = int(input())
print(2**n-1)
hanoi(n,1,3)