[Algorithm] 재귀 알고리즘_3(하노이의 탑)

05-3 하노이의 탑

하노이의 탑 알아보기

• 하노이의 탑(towers of Hanoi): 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제
• 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작하여 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮기는 문제
• 원반은 1개씩 옮길 수 있으며 큰 원반은 작은 원반 위에 쌓을 수 없다는 규칙을 지켜야 합니다.

[하노이의 탑 알고리즘]

 

하노이의 탑 알고리즘

[하노이의 탑 문제 풀이]

하노이의 탑 문제 풀이(원반 3개)

하노이의 탑 문제 풀이(원반 2개)

하노이의 탑 문제 풀이(원반 4개)

---

실습 5-6 하노이의 탑 구현하기

# 하노이의 탑 구현하기

def move(no: int, x: int, y: int) -> None:
  """원반 no개를 x기둥에서 y기둥으로 옮김"""
  if no > 1:
    move(no - 1, x, 6 - x - y)

  print(f'원반 [{no}]을(를) {x}기둥에서 {y}기둥으로 옮깁니다.')

  if no > 1:
    move(no - 1, 6 - x - y, y)

print('하노이의 탑을 구현합니다.')
n = int(input('원반의 개수를 입력하세요.: '))

move(n, 1, 3) # 1기둥에 쌓인 원반 n개를 3기둥으로 옮김

하노이의 탑을 구현합니다.
원반의 개수를 입력하세요.: 3
원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다.
원반 [2]을(를) 1기둥에서 2기둥으로 옮깁니다.
원반 [1]을(를) 3기둥에서 2기둥으로 옮깁니다.
원반 [3]을(를) 1기둥에서 3기둥으로 옮깁니다.
원반 [1]을(를) 2기둥에서 1기둥으로 옮깁니다.
원반 [2]을(를) 2기둥에서 3기둥으로 옮깁니다.
원반 [1]을(를) 1기둥에서 3기둥으로 옮깁니다.

이 프로그램에서는 기둥 번호를 정숫값 1, 2, 3으로 나타냅니다. 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 위치에 있든 중간 기둥은(6 - x - y)로 구할 수 있습니다. move() 함수는 no개의 원반을 다음과 같은 과정으로 이동합니다.

1. 바닥에 있는 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 1기둥에서 2기둥으로 옮깁니다.
2. 바닥에 있는 원반 [no]를 1기둥에서 3기둥으로 옮겼다는 것을 출력합니다.
3. 바닥에 있는 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 2기둥에서 3기둥으로 옮깁니다.

move() 함수의 동작(no = 3)

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%9E%AC%EA%B7%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습