[Algorithm] Programmers : 하노이의 탑 by Python

[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/12946

📌문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

한 번에 하나의 원판만 옮길 수 있습니다.
큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항
n은 15이하의 자연수 입니다.

입출력 예

입출력 예 설명
입출력 예 #1
다음과 같이 옮길 수 있습니다.

---

💡 문제 풀이

전형적인 재귀 호출 알고리즘이다.

하노이탑의 특징을 파악하여 원반 n개의 경우 최소로 옮기는 방법을 찾으면 된다.

원반 n개의 문제를 풀려면 원반 n-1개의 문제를 해결하면 된다.
→ 좀 더 작은 값으로 자기 자신을 호출

원반이 n개일 때

1. 1번 기둥에 있는 n-1개 원반을 2번 기둥으로 옮긴다.(n-1개 하노이의 탑 문제 풀기)

2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.
   

3. 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.(n-1개 하노이의 탑 문제 풀기)
   

하노이탑 알고리즘

1. 원반이 한 개면 옮기면 끝!(종료조건)
2. 원반이 n개일 때
   2-1. 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮긴다.(3번 기둥 옮기기 위한 보조기둥으로 사용)
   2-2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.
   2-3. 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮긴다.(1번 기둥을 옮기기 위한 보조기둥으로 사용)

코드는 다음과 같다.

def solution(n):
    answer = [] # 원판을 옮기는 순서를 담을 배열
    def hanoi(n, start, end, assist):
        nonlocal answer
        if n == 1: # 원판이 1개면 재귀 종료
            answer.append([start, end])
            return
        hanoi(n-1, start, assist, end) # 원반 n-1개를 assist로 이동 / end는 보조기둥
        answer.append([start, end])
        hanoi(n-1, assist, end, start) # assist에 있는 원반 n-1개를 end로 이동 / start는 보조기둥
    hanoi(n, 1, 3, 2) # 원판개수, 기둥번호(1 - 3 - 2 순)
    return answer