프로그래머스 level3 [하노이의 탑] 파이썬

# 프로그래머스 하노이의 탑


def hanoi(start, mid, end, pillar):
    if start:
        if start[1:]:
            return hanoi(start[1:], mid, end, [pillar[0], pillar[2], pillar[1]])+[[pillar[0], pillar[2]]]+hanoi(start[1:], mid, end, [pillar[1], pillar[0], pillar[2]])
        else:
            return [[pillar[0], pillar[2]]]


def solution(n):
    answer = []
    start = [i for i in range(n, 0, -1)]
    mid = []
    end = []
    answer = hanoi(start, mid, end, [1, 2, 3])
    return answer

3개의 고리를 각각 start, mid end 라고 하면,

n개의 고리이동 = n-1개의 고리를(start에서 mid로이동)+ 제일 큰 고리를 end로 이동 + n-1개의 고리를(mid에서 end로 이동)

이고, 위의 코드와 같이 짤 수 있다.

(사실 mid와 end 배열은 전혀 사용되지 않으므로 간결히 고치면)

 

# 프로그래머스 하노이의 탑


def hanoi(pillar, pillar_pos):
    if pillar:
        if pillar[1:]:
            return hanoi(pillar[1:], [pillar_pos[0], pillar_pos[2], pillar_pos[1]])+[[pillar_pos[0], pillar_pos[2]]]+hanoi(pillar[1:], [pillar_pos[1], pillar_pos[0], pillar_pos[2]])
        else:
            return [[pillar_pos[0], pillar_pos[2]]]


def solution(n):
    answer = []
    pillar = [i for i in range(n, 0, -1)]
    pillar_pos = [1, 2, 3]
    answer = hanoi(pillar, pillar_pos)
    return answer

현재 이동시킬 pillar와 pillar의 상대적인 위치가 담긴 배열을 hanoi 함수로 넘기고,

하노이 함수에서 위에서 언급했던 과정을 재귀적으로 반복하며, 값을 리턴한다.