하노이의 탑
작은 원반이 위에,큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해 원반을 옮기는 문제
크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작
작은 원반은 위에, 큰 원반은 아래에 쌓여 있음
원반은 1개씩 옮길 수 있으며 큰 원반은 작은 원반 위에 쌓을 수 없음
원반이 3개 일때
원반 1과 원반 2를 그룹으로 묶으면, 가장 먼저 이 그룹을 중간 기둥으로 옮긴 후에 가장 큰 원반 3을 목표기둥으로 옮김
총 3단계로 이동 가능
원반이 2개일때
원반 1을 그룹으로 본다면, 원반이 3개 일때와 동일하게 3단계로 이동 가능
원반이 4개일때
원반1,2,3을 그룹으로 묶으면 3단계로 이동 가능
원반 3개를 묶었던 그룹을 풀어서 이동
원반이 n개인 하노이 탑 문제 해결 가능
def move(no : int , x : int , y : int) -> None:
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)
binubibi