[level 3] Title: 하노이의 탑 파이썬

 

하노이 탑은 재귀로 풀어야한다고 들어보기만 하였다. 재귀는 아직 연습이 부족한지, 생각만 해도 머리가 지끈거린다...

현재의 내 머리로는 잘 이해가 가지 않아 유튜브 영상을 보고 이해 한 뒤, 코드를 작성했다.

 

참고한 유튜브 영상, 이해하는데 많은 도움이 됬다.

 

재귀함수에서는 종료 조건이 필수적이기에, n == 1일 때 answer에 값을 더해줌으로써 재귀를 멈추었다. 

 

def solution(n):
    answer = []
    
    def hanoi(n, start, end, mid):
        nonlocal answer
        if n == 1:      
            answer.append([start, end])
        else:
            hanoi(n-1, start, mid, end)
            answer.append([start, end])
            hanoi(n-1, mid, end, start)
        
    hanoi(n, 1,3,2)
    return answer

 

코드 제출 후, 다른사람들의 풀이를 보는데 다른건 다 이해가 가는데(찾아보고나서), 이건 이해가 잘 안간다..

def hanoi(f, t, m, n):
    if n == 0:
        return []

    return hanoi(f, m, t, n-1) + [[f, t]] + hanoi(m, t, f, n-1)


def solution(n):
    return hanoi(1, 3, 2, n)

공부를 더 해봐야할 듯하다..

 

 

코딩테스트 연습 - 하노이의 탑