19. 하노이의 탑 (재귀함수)

혼공파 70강

1. 하노이의 탑

 

# 3개의 기둥과 크기가 다른 원판들이 원뿔로 존재한다.
# 한번에 한 개의 원판만 옮길 수 있다.
# 큰 원판이 작은 원판 위에 있어서는 안된다.
# 기본적으로 원판의 개수가 n개 일때 2^n - 1회 움직여야 원판을 모두 옮길 수 있다고 알려져 있다.

# 원판의 개수가 4개 일 때 어떻게 옮겨야하는지 출력하는 프로그램 작성
카운터 = 0

def 하노이탑(원판개수, 시작기둥, 대상기둥, 보조기둥):
  global 카운터
  if 원판개수 == 1:
    print(시작기둥, "->", 대상기둥)
    카운터 += 1
  else:
    하노이탑(원판개수 - 1, 시작기둥, 보조기둥, 대상기둥)
    print(시작기둥, "->", 대상기둥)
    카운터 += 1
    하노이탑(원판개수 - 1, 시작기둥, 보조기둥, 대상기둥)

원판개수 = int(input("원판의 개수를 입력하세요: "))
하노이탑(원판개수, "A", "B", "C")
print(f" \n총 원판의 이동 횟수는 {카운터}입니다.")