[백준][19단계 재귀] 11729번 /하노이 탑 이동 순서 (파이썬/Python)

1. 문제 설명

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

2. 코드

import sys
input = sys.stdin.readline
n = int(input())
cnt = 0
out = []
def hanoi(k, a, b, c):
    global cnt
    if k == 0:
        return
    hanoi(k-1, a, c, b)
    out.append(f"{a} {c}\n")
    cnt += 1
    hanoi(k-1, b, a, c)

hanoi(n, 1, 2, 3)
sys.stdout.write(str(cnt)+"\n")
sys.stdout.write(''.join(out))

3. 풀이 과정

하노이 탑 문제는 3개의 기둥을 출발, 보조, 도착으로 나누어서 재귀를 진행해야 하는 문제이다.

재귀식의 핵심은 다음과 같다.

N개의 원판이 쌓여져 있다고 가정할 때,
1. N-1개의 원판을 보조로 옮긴다.
2. N번째 원판을 도착으로 옮긴다.
3. N-1개의 원판을 보조에서 도착으로 옮긴다.

k가 0이 되면 아무것도 반환시키지 않으면서 재귀를 끊는다.

출력값은 out에 이동 흐름을 저장시키고,

cnt에 횟수를 카운트한다.

출력할 때는 sys.stdout.write()으로 한번에 출력시켜 부하를 낮춘다.

단, 리스트나 정수는 사용 불가 하므로 cnt는 문자열로, out은 join()함수로 이어서 출력한다.