[백준] [재귀 분석 추가] 하노이의 탑 이동 순서 1759 (파이썬)

def hanoi(n, a, b):
    n > 1:
        hanoi(n-1, a, 6-a-b) # 기둥이 1개 이상이면 그룹으로 묶인 n-1개 원판을 중간으로 먼저 다 옮기겠다 1, 2, 3이기 때문에 중간은 1,3을 뺀 값

    print(a,b)               # n번 째 기둥이 a -> b 로 옮겨짐

    n > 1:                   # 기둥이 한개 이상이면 남은 기둥 (n-1)개를 중간에서 b로 옮기겠다.
        hanoi(n-1, 6-a-b, b)

n = int(input())

print(2 ** n-1) # 총 이동해야하는 횟수
hanoi(n, 1, 3) # 3개 원판을 기둥 1에서 3으로 옮기겠다

재귀함수 개념

2021.03.08 - [Algorithm & Data structure] - 재귀 함수

재귀 함수

하노이의 탑 재귀 분석 (추가 유투브 동영상)

www.notion.so/185deedd2003429caf7693b4dffe5185

하노이의 탑

youtu.be/qLJ3kHIuOKY

- YouTube

• hanoi (2,1,2)
  • hanoi(1,1,3)
    • n > 1: False
    • print 1 → 3 (1번)
    • n > 1: False
  • print 1 → 2 (2번)
  • hanoi(1,3,2)
    • n > 1: False
    • print 3 → 2 (3번)
    • n > 1: False

print 1 → 3 (4번)

• hanoi (2, 2, 3)
  • hanoi(1, 2, 1)
    • n > 1: False
    • print 2 → 1 (5번)
    • n > 1: False
  • print 2 → 3 (6번)
  • hanoi(1, 1, 3)
    • n > 1: False
    • print 1 → 3 (7번)
    • n > 1: False