[프로그래머스 lv3] 하노이의 탑 (재귀 문제)

문제 설명

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

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

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

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

제한사항

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

---

입출력 예

입출력 예

입출력 예 설명

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

 

 

 

 

---

나의 풀이

하노이의 탑의 기본 개념에 대해 알면 재귀적인 방법으로 어렵지 않게 풀 수 있다.

n개의 블록을 1->3 번으로 옮기는 방법 :
n-1개를 1번에서 2번으로 옮기고 남은 한 개를 3번으로 옮기고 2번에 옮겨놓은 n-1개의 블록을 3번으로 옮기면 된다.

그럼 n-1개의 블록을 어떻게 1번에서 2번으로 옮길까?

똑같은 원리를 사용하면 된다.

n-1개의 블록을 1->2 번으로 옮기는 방법 :
n-2개를 1번에서 3번으로 옮기고 남은 한 개를 2번으로 옮기고 3번에 옮겨놓은 n-2개의 블록을 3번으로 옮기면 된다.

...

1개의 블록을 1->2 번으로 옮기는 방법 :
그냥 옮기면 된다

 

첫 번째 풀이

def solution(n):
    return hanoi(n, 1, 3, [])

def hanoi(n, a, b, history): # n개, a -> b
    if n == 0: return
    
    hanoi(n-1, a, 6-(a+b), history)
    history.append([a, b])
    hanoi(n-1, 6-(a+b), b, history)
    
    return history

탑의 번호는 1, 2, 3 중 하나이다. 6-(a+b)의 의미는 만약 a: 1, b: 3이라면 6-(a+b)는 나머지 하나인 2를 나타내게 된다.

(1 + 2 + 3 =  6)

함수의 매개 변수로 history를 넘겨주게 되면 history의 값만 넘겨주는 것이 아니라 history 자체를 넘겨주게 된다. 그래서 받은 history에 append()를 그대로 실행해도 history에 계속해서 쌓이게 되는 것이다.

 

두 번째 풀이

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

def hanoi(n, a, b): # n개, a -> b
    if n == 0: return []
    return hanoi(n-1, a, 6-(a+b))+[[a, b]]+hanoi(n-1, 6-(a+b), b)

원리는 동일하다.

다만 n이 0일 때 리스트를 반환 해줘야 return 부분에서 다른 리스트와 결합할 수 있기 때문에 첫 번째 풀이와 return에서 차이가 있다. (첫 번째 풀이에서 n이 0일 때 return [] 을 해줘도 상관 없다)

(좌)첫 번째 코드 결과, (우)두 번째 코드 결과

 

첫 번째 방법은 기존의 리스트에 append를 하여 추가하는 방법이고, 두 번째 방법은 리스트를 결합하고 계속해서 새로 생성하기 때문에 약간의 시간 차이가 나는 것으로 생각된다.