[Python] 하노이 탑 이동 순서 - 재귀

11729 문제

해당 문제 링크

풀이

[풀이 1]

def hanoi(n, a, b, c):
    if n==1:
        move.append([a, c])
    else:
        hanoi(n-1, a, c, b)
        move. append([a, c])
        hanoi(n-1, b, a, c)

move=[] #이동 경로를 담을 list
hanoi(int(input()), 1, 2, 3)
print(len(move))
print("\n".join([' '.join(str(i) for i in row) for row in move]))

[풀이 2]

def hanoi(n, start, end) :
    if n==1:
        print(start, end)
        return
    
    hanoi(n-1, start, 6-start-end) #1단계
    print(start, end) #2단계
    hanoi(n-1, 6-start-end, end) #3단계

n = int(input())
print(2**n -1)
hanoi(n, 1, 3)

해석

[해석 1]

• n이 짝수일 때는 제일 먼저 1번판(a)에서 2번판(b)로 이동
• n이 홀수일 때는 제일 먼저 1번판(a)에서 3번판(c)로 이동

코드 및 해석 참고 사이트 -1

[해석 2]

• 1단계 에서는 start 막대에서 6-start-end 막대로 옮겼는데
  위 그림을 참고해보면 1단계에서는, start 막대(그림에서 1번 막대)에 있는 n개의 원판 중 n-1개의 원판을 end 막대(그림에서 3번 막대)가 아닌 2번 막대로 옮긴다.
  그런데 start와 end 막대의 번호만을 알고 있을 뿐 나머지 막대의 번호는 알지 못한다.
  start막대와 end막대 그리고 번호 모를 막대의 번호를 다 합치면 6이 되므로(1+2+3)
  결국, 6에서 start와 end를 빼주면 번호 모를 막대의 번호를 알게 된다.
• 2단계에서는 그림과 같이 start 막대에서 end막대로 옮겨주면 됩니다.
• 3단계의 경우 1단계와 마찬가지의 메커니즘이 작동합니다!

코드 및 해석 참고 사이트 -2