[파이썬] 하노이의 탑 - 재귀함수 ★

실습 설명

하노이의 탑 게임 아시나요? 이 게임의 목표는 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것입니다. 지켜야할 규칙은 두가지입니다.

한 번에 하나의 원판만 옮길 수 있다.
큰 원판이 작은 원판 위에 있어서는 안 된다.

(출저: 위키피디아)

하노이의 탑 게임의 해답을 출력해주는 함수 hanoi를 쓰세요. hanoi는 파라미터로 원판 수 num_disks, 게임을 시작하는 기둥 번호 start_peg, 그리고 목표로 하는 기둥 번호 end_peg를 받고, 재귀적으로 문제를 풀어 원판을 옮기는 순서를 모두 출력합니다.

 

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 가장 큰 원판을 제외하고 나머지를 str -> oth
        hanoi(num_disks - 1, start_peg, other_peg)
        
        #2 가장 큰 원판을 str -> end
        move_disk(num_disks, start_peg, end_peg)
        
        #3 나머지 원판들을 oth -> end
        hanoi(num_disks - 1, other_peg, end_peg)
    
    

# 테스트 코드 (포함하여 제출해주세요)
hanoi(3, 1, 3)

1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

가장 작은 원판의 번호는 1번이고 가장 큰 원판의 번호는 num_disks번입니다. 그리고 왼쪽 기둥이 1번, 가운데 기둥이 2번, 오른쪽 기둥이 3번입니다.

 

원판 하나인 경우

hanoi(1, 1, 3)

1번 원판을 1번 기둥에서 3번 기둥으로 이동

원판 두개인 경우

hanoi(2, 1, 3)

1번 원판을 1번 기둥에서 2번 기둥으로 이동
2번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 3번 기둥으로 이동

원판 세개인 경우

hanoi(3, 1, 3)

1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동

 

 

힌트 1
재귀 함수에는 recursive case와 base case가 있습니다.

Recursive case: 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
Base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

우선 base case가 무엇인지 생각해 볼까요?

 

힌트 2
일단 가장 쉬운 경우는 원판이 하나도 없을 때입니다. 아무것도 안 해도 게임이 끝나겠죠?

 

힌트 3
코드로 나타내면 이렇게 되겠습니다.

def hanoi(num_disks, start_peg, end_peg):
    # base case: 옮길 원판이 없으면 부분 문제를 나누지 않고 함수를 끝낸다
    if num_disks == 0:
      return

그럼 원판이 하나 이상에 있는 경우, 즉 recursive case 에는 문제를 어떻게 해결할 수 있을까요?

 

 

힌트 4
원판이 1 개밖에 없는 경우도 쉽죠? 1번 기둥에서 3번 기둥으로 옮기면 끝납니다.

 

 

힌트 5
원판이 2 개인 경우는 조금 더 생각을 해야합니다. 1번 원판을 1번 기둥에서 2번 기둥으로 옮기고, 2번 원판을 1번 기둥에서 3번 기둥으로 옮기고, 1번 원판을 2번 기둥에서 3번 기둥으로 옮기면 됩니다.

 

힌트 6
이제 원판 3 개인 경우입니다.

일단 3번 원판이 3번 기둥에 가야하는데, 그러기 위해서는 1, 2번 원판이 2번 기둥에 가있어야겠죠? 그런데 원판 2 개를 옮기는 것은 이미 '난이도 2'에서 했습니다. 그냥 그대로 따라하면 됩니다.

다만 ‘난이도 2’ 에서는 원판들을 1번 기둥에서 3번 기둥으로 옮기려고 했다면, 이번에는 1, 2번 원판들을 1번 기둥에서 3번 기둥으로 옮기는 차이가 있죠?

이걸 프로그래밍 방식으로 생각하면 hanoi 함수를 시작 기둥과 끝 기둥 인풋만 바꿔주고 재귀적으로 호출한다고 얘기할 수 있습니다. 그렇게 원판 2 개를 옮겼다고 가정합시다.

이제 원하던대로 3번 원판을 3번 기둥으로 옮기면 됩니다.

마지막으로 2번 기둥에 있는 원판 2 개를 3번 기둥으로 옮겨야 하는데, 이것도 '난이도 2'에서 한 것과 똑같이 하면 됩니다. 또 hanoi 함수를 부르는 셈이죠. 유일한 차이는 이번에는 1, 2번 원판을 2번 기둥에서 3번 기둥으로 옮겼다는거죠?

힌트 7
원판 4 개인 경우도 원판 3 개인 경우랑 똑같이 생각할 수 있습니다.

4번 원판을 3번 기둥으로 옮기기 위해서 그 위에 원판 3 개를 먼저 2번 기둥으로 옮겨야 합니다. 원판 3 개를 옮기는 것은 '난이도 3'에서 한 방식 그대로 하면 됩니다.

그리고 나서 4번 원판을 3번 기둥으로 옮기고…

다시 '난이도 3'의 방식대로 원판 3 개를 3번 기둥으로 옮기면 끝납니다.

원판들을 옮기는 과정이 이해가 되시나요?

위에서 설명한 알고리즘을 어떻게 정리할 수 있는지 생각해 보세요!

힌트 8
템플릿에서 hanoi함수에 들어가는 기둥 인풋들이 기억 나시나요? start_peg, end_peg였죠? 그리고 옮기려는 원판의 갯수가 num_disks입니다.

시작하는 기둥을 start_peg, 목표 기둥을 end_peg, 그리고 남는 하나의 기둥을 other_peg라고 부릅시다. 그러면 힌트 4에 나온 문제 풀이 방식을 이렇게 정리할 수 있습니다:

원래 문제가 num_disks 개의 원판을  start_peg에서부터 end_peg로 옮기는 문제였다면, 문제를 풀기 위해서 사용하는 알고리즘은 아래와 같습니다.

가장 큰 원판을 제외하고 나머지 원판들을 start_peg에서 other_peg로 이동
가장 큰 원판을 start_peg에서 end_peg로 이동
나머지 원판들을 other_peg에서 end_peg로 이동
이게 우리의 recursive case가 되겠죠?

힌트 9
아직도 어떻게 해야되는지 이해하시기 힘들 수 있어요,

일단 start_peg와 end_peg가 주어졌을 때 other_peg는 어떻게 구할까요? 1번 기둥, 2번 기둥, 3번 기둥이 있기 때문에 start_peg + end_peg + other_peg는 항상 6입니다. 따라서 other_peg는 이렇게 정의할 수 있겠네요

other_peg = 6 - start_peg - end_peg

이제 이 other_peg를 이용해서 힌트 4에 나오고 힌트 5에서 정리한 recursive case를 써 볼까요?