프로그래머스 - 하노이의 탑 (python 파이썬)

[level 2] 하노이의 탑 - 12946

문제 설명

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

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

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

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

제한사항

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

 

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

프로그래머스

 

---

 

맨 위부터 하나씩 옮기는 게 아니라 1개를 제외한 뭉탱이를 옮긴다고 생각하면 된다.

 

예를 들어, 1번에 3개가 있었다면

1. 1개만 두고 나머지 2개를 2번으로 옮긴다.

   (2번으로 옮기는 과정은 2번이 도착점이라고 생각하면 된다.)

2. 1번에 남은 1개를 3번에 옮긴다. 

3. 2번의 있는 2개를 다시 시작점으로 생각해서 반복한다.

 

 

이걸 n에 대한 값으로 다시 정리를 해보면

1. 시작점에서 개수가 1개뿐이라면 바로 도착점으로 가면 된다.

2. 시작점에서 1개를 제외한 n-1 개를 중간 지점으로 옮기는 과정을 계산한다.

3. 다 옮겼다면 시작점에 있는 1개를 도착점으로 옮긴다.

4. 중간 지점을 시작점으로 해서 다시 1단계부터 시작한다.

 

코드로 봐보자.

def hanoi(start, end, middle, answer, n):
	#1. 시작점에서 개수가 1개뿐이라면 바로 도착점으로 가면 된다.
    if n == 1:
        answer.append([start, end])
    else:
    	#2. 시작점에서 1개를 제외한 n-1 개를 중간 지점으로 옮기는 과정을 계산한다.
        hanoi(start, middle, end, answer, n-1)
        #3. 다 옮겼다면 시작점에 있는 1개를 도착점으로 옮긴다.
        answer.append([start, end])
        #4. 중간 지점을 시작점으로 해서 다시 1단계부터 시작한다.
        hanoi(middle, end, start, answer, n-1)
        
def solution(n):
    answer = []
    hanoi(1, 3, 2, answer, n)
        
    return answer

 

 

느낀 점

생각해내는 데 오랜 시간이 걸렸다. 재귀 함수 사용에 대한 연습이 더 필요할 것 같다..!!