[ 프로그래머스 / PYTHON ] 하노이의 탑

문제 설명

하노이의 탑
한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

[입출력 예]

n	result
2	[ [1,2], [1,3], [2,3] ]

설명

하노이의 탑 =재귀

🔎한번 더 푼 후기
이거 작년 교수님 설명때부터 저번에 풀때까지 보일때마다 헷갈리더니 이제는 10분도 안돼서 풀어버려따! 'n-1개를 서포트로 옮기고, 맨 밑을 end로 옮기고, 다시 서포트를 end로 옮겨준다 + n이 1이면 바로 end로 옮겨준다' 만 기억하면 쉽다.

코드

22.06.27 코드

answer = []
def hanoi(n,st,sp,end):
    global answer
    if n == 1:
        answer.append([st,end])
        return
    else:
        hanoi(n-1,st,end,sp)
        answer.append([st,end])
        hanoi(n-1,sp,st,end)

def solution(n):
    hanoi(n,1,2,3)
    return answer

22.08.05 코드

def solution(n):
  answer = []
  def hanoi(n,st,sp,end):
      nonlocal answer
      if n == 1:  answer.append([st,end])
      else:
          hanoi(n-1,st,end,sp)
          answer.append([st,end])
          hanoi(n-1,sp,st,end)
  hanoi(n,1,2,3)
  return answer