[PS / PYTHON] 12946. 하노이의 탑.

문제.

풀이.

하노이의 탑 이동 과정은

A -> B
A -> C
B -> C

이다.

위의 과정을 반복해서 동작하는 것이고, A 는 출발지, B 는 임시 거처, C 는 목적지로 생각하면 된다.

N = 2 일 때 는 위의 과정으로 움직인다.
N = 3 일 때 첫번째 A -> B 과정은 위의 두 개의 원판을 B 로 움직이는 것이기 때문에, 두 개의 원판이 출발지 A, 임시거처 C, 목적지 B 로 설정되고 움직인다.
두번째 A -> C 과정은 맨 아래의 원판 하나를 움직이는 것이기 때무에 그대로 설정한다.
마지막 B -> C 과정은 B 에 있는 두 개의 원판을 C 로 이동 시키기 위해서 출발지 B, 임시거처 A, 목적지 C 로 설정하고 움직인다.

코드.

def solution(n):
    answer = []

    def hanoi(N, FROM, TEMP, TO):
        if N == 1:
            answer.append([FROM, TO])
            return

        hanoi(N-1, FROM, TO, TEMP)
        answer.append([FROM, TO])
        hanoi(N-1, TEMP, FROM, TO)

    hanoi(n, 1, 2, 3)

    return answer