[알고리즘] 하노이의탑

설명)

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

 

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안된다.

 

(출저: 위키피디아)

 

하노이의 탑 게임의 해답을 출력해주는 함수 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):
    # 여기에 코드를 작성하세요

# 테스트 코드 (포함하여 제출해 주세요)
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. 원판이 한개 밖에 없는 경우

1번기둥에서 3번 기둥으로 옮기면 끝난다.

 

원판이 2개인 경우

1번 원판을 1번 기둥에서 2번 기둥으로 옮기고, 2번 원판을 1번 기둥에서 3번 기둥으로 옮기고, 1번 원판을 2번기둥에서 3번 기둥으로 옮기면 된다.

 

원판이 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번기둥으로 옮겼다는 것

 

 

원판이 4개인 경우도 원판 3개인 경우랑 똑같이 생각 할 수 있음.

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

 

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

 

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

 

답안)

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)

# 테스트 코드
hanoi(3, 1, 3)