Programmers - 하노이의 탑

문제 링크

유명한 재귀 문제

각 기둥의 이름이 1,2,3일 때, 1에 있는 N개의 원반을 3으로 이동하는 방법

1. 1의 N-1개 원반을 2(경유지)로 보낸다
2. 1의 남은 1개 원반(가장 밑에 있는 원반)을 3으로 보낸다
3. 2의 N-1개 원반을 3으로 보낸다

get_stopover(x,y) : fr,to 가 주어질 때 중간 경유지를 구하는 함수
hanoi(fr,to,count) : fr에 있는 원반 count 개를 to로 이동하는 함수

def solution(n):
    answer = []

    def get_stopover(x, y):
        if x+y == 3:
            return 3
        if x+y == 4:
            return 2
        return 1

    def hanoi(fr, to, count):
        if count == 1:
            answer.append([fr, to])
            return

        stopover = get_stopover(fr, to)
        hanoi(fr, stopover, count-1)
        hanoi(fr, to, 1)
        hanoi(stopover, to, count-1)

    hanoi(1, 3, n)

    return answer