하노이의 탑 - Python

문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항
n은 15이하의 자연수 입니다.

입출력 예

문제해결과정

1. 하노이의 탑은 원리는 다들 알꺼라고 생각한다. 핵심로직은 other_peg = 6 - start_peg - end_peg 이다. 6을 빼준이유는 하노이 계산 시 원판을 1, 2, 3로 옮길때 계산되는 횟수를 다 더한것이고 other_peg를 구하기 위해 이런 규칙을 만들어 낸 것이다. ex) 1, 2, 3 중 2개를 골라서 6을 빼면 나머지 숫자가 나온다.

---

def solution(n):
    answer = []
    hanoi(n, 1, 3, answer)
    return answer

def move_disk(disk_num, start_peg, end_peg, answer):
    answer.append([start_peg, end_peg])
    
def hanoi(num_disks, start_peg, end_peg, answer):
    # 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, answer)
        
        # 2. 가장 큰 원판을 start_peg에서 end_peg로 이동
        move_disk(num_disks, start_peg, end_peg, answer)
        
        # 3. 나머지 원판들을 other_peg에서 end_peg로 이동
        hanoi(num_disks - 1, other_peg, end_peg, answer)