하노이 탑

---

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

---

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100)이 주어진다.

---

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

N이 20 이하인 입력에 대해서는 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다. N이 20보다 큰 경우에는 과정은 출력할 필요가 없다.

---

문제 풀이

식 정리과정

위에 정리한 것을 정리하면, 하노이 탑에서 집중할 것은 원판 n-1개를 2번째 봉에 쌓은 후, 3번째 봉에 n번째 제일 큰 원판을 옮기고 나머지 원판을 옮겨주는 것이다.

그래서 해당 원판 이동횟수 $T(N)$을 정리하면

$T(N)$ $=$ $2T(N-1)$ $+$ $1$ 이 된다.

해당 식을 $1$ 부터 $N$ 까지 넣어보면

$T(1)=1\\T(2)=2T(1)+1=3\\T(3)=3T(2)+1=7\\T(4)=4T(3)+1=15$

해당 값을 보면 1,3,5,7,15 순으로 일정한 패턴이 보인다.

$T(N)=2^n+1$

$T(N)$은 이진 트리의 노드 개수와 동일하다.

이진 트리에 대해서는 밑에 그림 참고

이걸 코드로 구현하게 된다면, 재귀 함수를 이용하여, 노드를 구성할 수 있다.

노드를 구성하게 된다면 해당 처럼

루트 : 큰 원반 목적지로 옮기기
왼쪽 : (N-1)개 원반 보조 기둥으로 옮기기
오른쪽 : (N-1)개 원반 다시 목적지로 옮기기

이렇게 구성될 것이다.

그래서 재귀함수를 구성할 때 순차적인 과정 출력을 위해 중위 순회를 하여 print문을 출력할 것이다.

중위 순회 과정을 출력하기 위해서는 print문을 재귀함수 사이에 넣으면 된다.

재귀함수에서 순회에 따른 출력은 이걸 참조하자 !

재귀 함수에서 순회에 따른 출력

전위 순회 : 재귀 함수 위에 위치
중위 순회 : 재귀 함수 사이에 위치
후위 순회 : 재귀 함수 밑에 위치

---

코드

#해당 함수는 첫세팅이다.
#시작되는곳에 제일 작은것을 끝기둥에 올리는 작업.

def hanoi(n, start, auxiliary, end) : 
    if n == 1 : #하나일떄 가장큰거 목적지로 올려버리는 연산
        print(start, end)
        return
    
    #재귀함수의 매개변수가 헷갈릴땐 
    # 원반이 4개일 때를 생각해보자.
    #해당 함수는 원반들을 보조기둥으로로 이동시키는 것
    hanoi(n-1, start, end, auxiliary)
    print(start, end)
    #해당 함수는 2번에 있는 원반들을 3번으로 이동시키는것것
    hanoi(n-1, auxiliary, start, end)

n = int(input())
print(2 ** n - 1)
if n <= 20 : hanoi(n, 1, 2, 3)