[백준] 11729 하노이 탑 이동 순서

문제

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

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

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

입력

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

출력

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

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

 

#coding=utf-8
 
 
#  문제
#
# 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
#
#     한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
#     쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
#
# 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
#
# 입력
#
# 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
#
# 출력
#
# 첫째 줄에 옮긴 횟수 K를 출력한다.
#
# 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
 
 
 
# 이제 하노이 탑을 소스 코드로 만들어보자.
#
# 1. n 개의 원반이 있을 때 n - 1개의 원반은 첫 번째 칸에서 두 번째 칸으로 이동한다.
#
# hanoi(n - 1, from, to, by)
#
# 2. n 번째 원반을 첫 번째 칸에서 세 번째 칸으로 옮긴다.
#
# move(from, to)
#
# 3. 두 번째 칸에 있는 n - 1개의 원반을 세 번째 칸으로 이동한다.
#
# hanoi(n - 1, by, from, to)
 
 
# def T(N, Beg, Aux, End):
#     if N == 1:
#         print(Beg, '->', End)
#
#     else:
#         T(N-1, Beg, End, Aux)
#         T(1, Beg, Aux, End)
#         T(N-1, Aux, Beg, End)
 
 
import sys
input=sys.stdin.readline
 
move_cnt=0
move_log=[]
 
def move(x, first_stick, second_stick, third_stick):
    if x==1:
        move_log.append([first_stick,third_stick])
        #print(first_stick, third_stick)
        return
 
    else:
        move(x-1, first_stick, third_stick, second_stick)   #세번째 스틱을 보조로 첫번째 스틱에서 두번째 스틱으로 옮김. x를 줄여가며 남은 원반이 1이 될때까지 재귀
        move(1,first_stick, second_stick, third_stick)  #x==1을 주어서 원반의 이동을 출력하기위해서 재귀함수 호출(이동 기록)
        move(x-1, second_stick, first_stick, third_stick)   #두번째 스틱으로 넘긴 원반을 첫번째 스틱을 보조로 세번째 스틱으로 옮김. x를 줄여가며 남은 원반이 1이 될까지 재귀
 
disk=int(input())
move(disk,1,2,3)
print(len(move_log))
for i in range(0,len(move_log)):
    for j in range(0,2):
        print(move_log[i][j],"",end='')
    print()