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

문제

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

풀이

하노이 탑에 대해서는 위키를 참고하자.
문제의 출력 예시에서 규칙을 찾아낼 수 있다.
하노이 탑 봉을 left, mid, right로 표기하고 설명하겠다.

# 입력 예시
3

# 출력 예시
7
1 3 #1
1 2 #2
3 2 #3
1 3 #4
2 1 #5
2 3 #6
1 3 #7

• #1~#3: left -> right -> mid 를 거쳐서 n-1개의 원판을 옮긴다.
• #4: 가장 큰 n번 원판을 최종 목적지 right로 옮긴다.
• #5~#7: mid -> left -> right 를 거쳐서 n-1개의 원판을 옮긴다.

3개의 과정을 재귀로 표현하면 완성된다.

def hanoi(n, left, mid, right, answer):
    if n == 1: answer.append(str(left) + " " + str(right))
    else:
        hanoi(n-1, left, right, mid, answer) # 1~3 과정
        answer.append(str(left) + " " + str(right)) # 4 과정
        hanoi(n-1, mid, left, right, answer) # 5~7 과정

N = int(input())
answer = []
hanoi(N, 1, 2, 3, answer)
print(len(answer))
for a in answer:
    print(a)