[프로그래머스] 하노이의 탑- 파이썬/python

문제

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

프로그래머스

하노이 탑의 세 개의 기둥과 이 기둥에 꽂을 수 있는 다양한 크기의 원판이 있다. 두 가지 조건을 만족하면서, 한 기둥에 꽂힌 원판들을 다른 기둥으로 옮겨서 다시 쌓는 것이다. 기둥 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 기둥으로 최소 횟수로 옮기는 문제다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 큰 원판이 작은 원판 위에 있어서는 안 됩니다.

 

제한사항

• n은 15 이하의 자연수입니다.

 

예시

n : 2
result : [[1,2], [1,3], [2,3]]

 

이해를 돕기 위한 예시 사진

 

풀이

문제를 보고 전혀 감이 오지 않아서 유튜브를 참고해서 풀었다.

def hanoi(num, start, temp, end):
    if num == 1:
        return [[start, end]]
    return hanoi(num - 1, start, end, temp) + hanoi(1, start, temp, end) + hanoi(num - 1, temp, start, end)

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

• 이동해야 할 원판이 하나(num == 1)라면 단순히 그 원판을 시작 기둥에서 마지막 기둥으로 옮기는 값을 반환한다.
• 그렇지 않을 경우에는 세 단계를 수행하면서 재귀적으로 푼다.
  • 'num - 1'개의 원판을 시작 기둥에서 임시 기둥으로 옮긴다.
  • 하나의 원판(가장 마지막 원판)을 시작 기둥에서  마지막 기둥으로 옮긴다.
  • 'num - 1'개의 원판을 임시 기둥에서 마지막 기둥으로 옮긴다.

 

참고자료

https://www.youtube.com/watch?v=vq7dpFWpwAE