[프로그래머스] lv2 하노이의 탑_python

간만에 다시 푸는 하노이의 탑.
다시 풀어도 드는 생각, 왜 이게 lv2? 알고리즘을 생각하기 어렵기도 하고, 맞게 동작해도 제대로 이해된게 맞나 싶다.
무튼 문제를 풀어보자.

일단 하노이의 탑은 워낙 유명하니 간략하게 설명하면,
1번 기둥의 모든 고리를 3번 기둥으로 옮기면 된다. 단, 크기순 배열을 곁들인...
그림을 보면 이해는 쉽다.

프로그래머스 하노이의 탑

n=2(고리 2개)는 보기가 너무 적어 설명이 어려우니 n=3으로 가정하자.
n=3(고리 3개)인 상황
 1번 기둥의 가장 큰 고리는 3번 기둥으로 옮기려면 그전까지의 고리를 모두 2번 기둥으로 옮겨야한다.
즉, 우리는 n번째의 고리를 옮기기 위해 n-1개의 고리를 2번 기둥으로 옮겨야 한다.
이후 1번에 남은 n번 고리를 3번 기둥으로 옮긴다.
다시 2번기둥에 있는 n-1개의 고리를 3번 기둥으로 옮겨야 한다.
그럼 끝.
그리고 결국 고리는 1개씩 움직여야하니 종료조건은 n==1일때로 해주면 되겠다.

def solution(n):
    answer = []
    def hanoi(start, target, mid, n):
        if n == 1:
            answer.append([start, target])
            return
        hanoi(start, mid, target, n-1)
        hanoi(start, target, mid, 1)
        hanoi(mid, target, start, n-1)

    hanoi(1, 3, 2, n)
    return answer