[프로그래머스 Lv2,python]- 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946#

프로그래머스

def solution(n):
    res = []
    stack = [(n,1,3,2)] # 원반 개수, 출발기둥, 목표 기둥, 보조 기둥
    
    while stack:
        disks, start, end, tmp = stack.pop()
        
        if disks == 1:
            res.append([start, end])
        else:
            stack.append((disks-1, tmp, end, start)) # 보조->목표
            stack.append((1, start, end, tmp)) # 가장 큰 원반 이동
            stack.append((disks-1, start, tmp, end)) # 원반->보조
    return res

def solution(n):
    res = []
    
    def hanoi(disks, start, end, tmp):
        if disks == 1:
            res.append([start, end])
        else:
            hanoi(disks-1, start, tmp, end) # 원반->보조
            hanoi(1, start, end, tmp) # 가장 큰 원반 이동
            hanoi(disks-1, tmp, end, start) # 보조->목표
             
    hanoi(n, 1, 3, 2)
    return res

 

문제를 푸는 방식은 아래와 같다.

1) 1번 기둥에 있는 (n-1)번 원반들을 중간 기둥으로 옮긴다

2) 1번 기둥에 있는 n번 원반들을 3번 기둥으로 옮긴다

3) 중간 기둥에 있는 (n-1)번 원반들을 3번 기둥으로 옮긴다