하노이의 탑(Tower of Hanoi)
원반 옮기기 퍼즐
크기가 다른 원반 n개와 원반을 끼울 수 있는 기둥 3개가 존재한다.
어떻게 하면 원반 n개를 Start 기둥에서 Goal 기둥으로 옮길 수 있는가? 제약 사항은 아래와 같다.
- 원반은 한 번에 한 개 씩만 옮길 수 있다.
- 각 기둥 맨 위의 원반은 다른 기둥의 맨 위로만 움직일 수 있다.
- 옮기는 과정에서 큰 원반을 작은 원반 위에 올릴 수는 없다.
풀이 방법
- 원반이 한개인 경우
- 원반이 n개인 경우
즉, 원반이 1개일 때가 종료 조건인 재귀 함수로 하노이의 탑 알고리즘을 구현할 수 있다.
코드 구현
def hanoi(n, from_p, to_p, aux_p): # 매개변수 n은 원반 수, from_p는 출발 기둥, to_p는 도착 기둥, aux_p는 보조 기둥
if n == 1:
print(f"{from_p} -> {to_p}")
return
hanoi(n - 1, from_p, aux_p, to_p) # 보조 기둥으로 이동
print(f"{from_p} -> {to_p}")
hanoi(n - 1, aux_p, to_p, from_p) # 도착 기둥으로 이동n개의 원반을 옮기는 횟수는 \( 2^n-1 \) 이므로 알고리즘의 계산 복잡도는 \( O(n^2) \) 이다.
참고문서
728x90