[알고리즘] 하노이 탑(recursion)

Function

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):
    if num_disks == 1:
        return move_disk(num_disks,start_peg,end_peg)

    other_peg = 6 - start_peg - end_peg
    
    hanoi(num_disks-1,start_peg,other_peg)
    move_disk(num_disks,start_peg,end_peg)
    hanoi(num_disks-1,other_peg,end_peg)

 

Test

 

Algorithm

1. 원반이 1개(n==1)일 때, 원반을 3번 기둥으로 옮기면 끝! (escape routine)

2. 원반이 n개 (n > 1)일 때,

  1) 가장 큰 원반을 제외한 n-1개 원반을 2번 기둥으로 옮긴다.

  2) 가장 큰 원반을 3번 기둥으로 옮긴다.

  3) 2번 기둥의 n-1개 원반을 3번 기둥으로 옮긴다. 

 

Recursion

hanoi(3,1,3)

위 test 코드에서 recursion 되는 함수 실행 흐름을 따라가보자.

우선, num_disks == 3 이므로 if문에 걸리지 않고 내려간다. 그 다음 호출되는 함수는 hanoi(2, 1, 2), 다시 함수 맨 위로 올라간다. num_disks == 2 이므로 if을 지나 hanoi(1, 1, 3)를 호출한다. 이는 if문에 걸려 첫 return값을 가진다. 그리고 밑으로 내려가 move_disk(2, 1, 2)를 호출하고 return한다. 다음, hanoi(1, 3, 2)를 호출하고 num_disks == 1이므로 return값을 가진다.

여기까지가 1) 가장 큰 원반을 제외한 n-1(2)개 원반을 1번기둥에서 2번 기둥으로 옮겨주는 함수 hanoi(2, 1, 2) 가 호출되어 return되는 과정이다. hanoi(2, 1, 2)가 return 되었으니, 밑으로 내려갈 수 있다. 2) 가장 큰 원반을 1번에서 3번 기둥으로 옮기는 함수 move_disk(3, 1, 3)이 호출되고 바로 return된다. 그리고 내려가서 3) 2번 기둥의 n-1(2)개 원반을 2번에서 3번 기둥으로 옮기는 함수 hanoi(2,2,3)가 호출된다.