[알고리즘] 하노이탑

개념

1. 처음에 모든 원판은 A기둥에 꽂혀 있다.
2. 모든 원판의 지름은 다르다.
3. 이 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
4. 작은 원반 위에 큰 원반을 놓을 수 없다.
5. 한 번에 하나의 원판(가장 위에 있는 원판) 만을 옮길 수 있다.

코드

def hanoi(n, from_obj, to_obj, aux_obj):
    if n == 1:
        print(f'{from_obj}->{to_obj}')
        return
    hanoi(n-1, from_obj, aux_obj, to_obj)
    print(f'{from_obj}->{to_obj}')
    hanoi(n-1, aux_obj, to_obj, from_obj)

if __name__ == '__main__':
    print('n=======>1')
    hanoi(1, 'A', 'B', 'C')
    print('n=======>2')
    hanoi(2, 'A', 'B', 'C')

결과

» python3 playground.py
n=======>1
A->B
n=======>2
A->C
A->B
C->B
n=======>3
A->B
A->C
B->C
A->B
C->A
C->B
A->B

Reference

제주 코딩 베이스 캠프 코딩 페스티벌 python 100제