[ BOJ / 파이썬 ] 11729. 하노이 탑 이동 순서

와.. 정말 초등 기초 교구느낌이었던 하노이 탑인데.. 생각해보면 나는 어렸을 때 풀어본 적이 없다.

하하 그래서일까 꽤 버거웠다.

 

핵심은 반복되는 재귀 구조의 일반항을 찾아내는 것.

function(n) 에서 function(n-1)을 이용한 function(n)의 내용을 정리하는 게 핵심이었다.

 

사실 이게 재귀 문제의 핵심이라 어려운 부분인데.. 그래서 더 끈질기게 이 문제 잡고 늘어지면서 이해를 했던 것 같다. 

어떤 문제를 만나도 잘 풀어낼 수 있도록 문제 자체에서 그 방식을 읽어내는 사고를 갖고자 했다.

 

정말 ! 정말 ! 도움이 많이 됐던 글.. ( 링크 )

 

위의 글을 참고해서 풀어낸 코드. 

정답.

def move(k, start, to):
  global result
  result.append((start, to))

def hanoi(N, start, to, via):
  global hanoiCount
  hanoiCount += 1
  if N == 1:
      move(1, start, to)
  else:
      hanoi(N-1, start, via, to)
      move(N, start, to)
      hanoi(N-1, via, to, start)
hanoiCount = 0
result = []
def main():
  n = int(input())
  hanoi(n, 1, 3, 2)

  print(hanoiCount)
  for i in range(len(result)):
    print(*result[i])
      
if __name__ == '__main__':
  main()

 

 

이전에 다른 풀이를 보고 어찌어찌 이해하고 넘어간 코드가 있는데 지금 생각해보면 수박 겉핥기식으로 이해했다하고 그냥 복붙해서 낸 것 같다.

def hanoi(n, start, end):
    if n > 1:
        hanoi(n-1, start, 6-start-end)
    print(start, end)
    if n > 1:
        hanoi(n-1, 6-start-end, end)
n = int(input())
print(2**n - 1)
hanoi(n, 1, 3)