문제

11729번 하노이 탑 이동순서

풀이

피보나치 수열과 더불어 가장 대표적인 재귀를 사용하는 문제이다. 핵심 아이디어와 코드도 매우 간단하고, 접해본지도 오래되었지만 완벽한 이해는 쉽지 않은 그런 문제이다. 최근에 하노이 탑을 비롯한 재귀(recursion)를 이해하는 방식으로 절차적(진행 과정을 따라가보는) 방식이 아닌 귀납적(k까지 잘 동작한다면, k+1에서는 어떻게 동작하게 할 것인지) 방식으로 생각하는 방식을 접한 뒤에는 문제 풀기가 훨씬 편해졌다.

f(n(원판의 개수), n개의 원반이 꽂힌 축, 옮기고자 하는 축, 나머지 한 축)
n개의 원판을 a에서 c로 옮긴다고 하면 f(n,a,c,b)가 되고,
이는 n-1개의 원판을 a->b, 가장 큰 n번째 원판을 a->c, 다시 n-1개의 원판을 b->c로 옮기는 과정으로 쪼갤 수 있다.

그대로 코드로 옮긴다. f(n-1,,,)과정이 제대로 수행된다면 f(n,,,)도 제대로 수행될 것임을 알 수 있다. 다만 종료조건 n==0 일 때 return None을 추가한다.

코드

n = int(input())
def f(n, a,c,b):
  if n==0: return None
  f(n-1,a,b,c)
  print('%d %d' %(a,c))
  f(n-1,b,c,a)
print(2**n-1)
f(n,1,3,2)