[ Lv 3 ] 하노이의 탑

문제 설명

---

풀이 과정

---

1. 재귀를 배우게 되면 가장 많이 배우게 되는 하노이의 탑 문제이다.

2. 1번에서 3번으로 맨 아래의 원판을 옮기기 위해서는 다음과 같은 과정을 거친다.
   2-1) 1번에서 자기 위의 원판들을 2번으로 옮겨 둔다.
   2-2) 1번의 가장 아래 원판을 3번으로 이동한다.
   2-3) 2번으로 옮겨둔 자기 위의 원판들을 3번으로 이동시킨다.

3. 위 과정을 재귀로 작성하면 문제가 풀리게 된다.

---

def hanoii(answer, n, src, temp, dest):
    if n == 1:
        answer.append([src, dest])
    else:
        hanoii(answer, n-1, src, dest, temp)
        answer.append([src, dest])
        hanoii(answer, n-1, temp, src, dest)

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

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges