링크 : [프로그래머스] 하노이의 탑, 파이썬

💡 문제 해결 아이디어

내가 생각한 아이디어

• 일단 하노이의 탑을 해본 적이 있다면, 이해가 훨씬 수월할 것이라는 점이다.
• 4개짜리 하노이 탑을 옮기려면, 3개짜리를 목표지점이 아닌 곳에 옮기고, 4번째(가장 큰) 원판을 목표지점에 옮긴 후에, 3개짜리를 목표지점에 옮기면 된다.
• 그러니, 큰 문제를 작은 문제로 쪼갤 수 있는 상황이라서 재귀(recursive call)로 해결할 수 있다!

💻 작성된 코드(수정)

def solution(n):
    def hanoi(num, start, end):
    	# 1개짜리 탑 즉 가장 작은 원판은 그냥 목표지점으로 옮기면 된다
        if num == 1:
            return [[start, end]]
        # 그게 아니라면, 출발/도착이 아닌 another의 위치를 알아야 한다.
        another = 0
        for i in range(1,4):
            if i != start and i != end:
                another = i
                break
        # n-1개짜리 탑을 다른 지점에 옮기고, n번째 원판을 목표지점에 옮기고, n-1개를 목표 지점으로 옮기면 된다!
        return hanoi(num-1, start, another) + [[start, end]] + hanoi(num-1, another, end)
    # n개짜리 탑을, 1번 지점에서 3번지점으로 옮기는 call을 하면 끝
    return hanoi(n, 1, 3)