1. 문제 설명

하노이의 탑

2. 문제 분석

전형적인 재귀 문제로 '완료 상황'과 '진행 상황' 조건을 그대로 입력한다. 마법 같은 재귀...라고 생각하지만, 사실 재귀는 아직 내게 어렵다. 하노이의 탑 문제를 정리하면 다음과 같다.

1. FROM, BY, TO라는 세 개의 기둥이 주어진다. N개의 원반이 FROM에 존재하고, TO로 N개의 원반 모두를 옮겨야 한다. 이때 원반 각각은 자신보다 크기가 작은 원반 위에 위치할 수 없다. (기본적인 하노이의 탑 조건)
2. 만일 한 개의 원반을 옮긴다면 FROM에서 TO로 바로 옮기면 된다. (문제 완료)
3. 다수의 원반을 옮긴다면 FROM에 존재하는 가장 '큰' 원반 하나를 TO에 옮기자. 이를 위해 가장 '큰' 원반 위의 N-1개를 BY로 치워놓아야 한다. 그리고 다시 BY를 원위치시키고, 이를 N이 1개 남을 때까지 반복하자.

3. 나의 풀이

def solution(n):
    result = []

    def hanoi(n, fr, by, to):

        if (n==1):
            result.append([fr, to])
            return

        hanoi(n-1, fr, to, by)
        result.append([fr, to])
        hanoi(n-1, by, fr, to)

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