[AL] 하노이의 탑

하노이의 탑 문제는 재귀 문제로 해결할 수 있다.

원반이 하나도 없을때 종료할 수 있다.

원반이 한 개 있을 때, 우리는 Tower 1에 있는 원반 하나를 Tower 3를 옮기면 성공이다.

원반이 두 개 있을 때, 작은 원반이 Tower2에 위치한다고 가정하고 풀면 Tower1에 원반을 tower3에 옮기고

원반 1개의 문제를 해결한다.

원반이 세 개 있을 때, 원반이 2개 쌓인게 Tower2에 위치한다고 가정하고 푼다면 Tower1 -> tower3,

원반 2개의 문제를 해결 하는 것과 같다.

원반이 4개 있을 때, 원반 3개 쌓인 것이 Tower 2에 위치한다고 가정하자.

원반 3개의 문제를 해결 하는 것과 같다. ,

이는 다음과 같은 구조를 갖는다.

원반 N개 문제 ->큰 원반 1에서 3으로, 원반 N-1개 문제 ->큰 원반 1에서 3으로, 원반 N-2개 .... 원반 4개 -> 원반 3개 -> 큰 원반 1에서 3으로,원반 2개 -> 큰 원반 1에서 3으로-> break

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))
    
def hanoi(num_disks, start_peg, end_peg):
    # base case: 옮길 원판이 없으면 부분 문제를 나누지 않고 함수를 끝낸다
    if num_disks == 0:
        return
    else:
        other_peg = 6 - start_peg - end_peg
        
        # 1. 가장 큰 원판을 제외하고 나머지 원판들을 start_peg에서 other_peg로 이동
        hanoi(num_disks - 1, start_peg, other_peg)
        
        # 2. 가장 큰 원판을 start_peg에서 end_peg로 이동
        move_disk(num_disks, start_peg, end_peg)
        
        # 3. 나머지 원판들을 other_peg에서 end_peg로 이동
        hanoi(num_disks - 1, other_peg, end_peg)