[Python] 프로그래머스 - 하노이의 탑

문제

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

프로그래머스

풀이

나의 풀이

def solution(n):
    answer = []
    
    def func(n):
        # n층의 결과값 만드는 함수
        # n-1층
        h = len(floor[n-1])//2
        # n-1층의 절반
        h1 = floor[n-1][:h]
        h1 = [h1[0][::-1]]+h1[1:] # 첫번째 원소 반전
        # 나머지 절반
        h2 = floor[n-1][h:]
        h2 = [h2[0][::-1]]+h2[1:] # 첫번째 원소 반전
        n1 = h1+h2
        # n-2층
        n2 = floor[n-2]
        # n층 결과
        res = n2+n1+n2
        return res
    
    floor = [[] for _ in range(16)]
    if n%2==0:
        floor[1] = [[1,2]]
        floor[2] = [[1,3],[2,3]]
        
    else:
        floor[1] = [[1,3]]
        floor[2] = [[1,2],[3,2]]
    for i in range(3,n+1):
        floor[i] = func(i)
    
    for i in range(n+1):
        answer+=floor[i]
    
    return answer

팬시한 코드는 아니지만, n층의 탑이 있다고 할 때 탑의 일부분이 똑바로 세워지기 위해서 어떤 결과가 나오는지를 분석해서

위와 같은 점화식을 세울 수 있었다.

 

예시 : n = 3

n=3인 탑을 규칙에 맞게 세번째 봉으로 옮기기 위해서는 다음과 같은 과정을 거쳐야 한다.

1. 1,2층의 블럭을 두번째 봉으로 옮긴다.
2. 세번째 층을 세번째 봉으로 옮긴다.
3. 두번째 봉의 2개의 층을 세번째 봉으로 옮긴다.

잘 생각해보면 n이 어떤 값이던지 위의 세가지 과정은 동일하게 이루어짐을 알 수 있다.

따라서, 위의 세 과정을 일반화 하면

1. n-1층의 탑을 두번째 봉에 세운다
2. n층을 세번째 봉으로 옮긴다.
3. 두번째 봉의 n-1층의 탑을 세번째 봉으로 옮긴다.

나는 이 점을 참고해 n층의 탑을 옮기기 위해서는 1, 2, ..., n-1층의 부분적인 탑이 그 과정에서 세워져야 했음에 주목하였고

각 부분 탑이 세워지는데 어떤 과정이 소요되는지를 살펴보며 패턴을 파악하려고 하였다.

(n=1)

1 : [1,3]



(n=2)

1 : [1,2]

2 : [1,3],[2,3]



(n=3)

1 : [1,3]

2 : [1,2],[3,2]

3 : [1,3],[2,1],[2,3],[1,3]



(n=4)

1 : [1,2]

2 : [1,3], [2,3]

3 : [1,2], [3,1], [3,2], [1,2]

4 : [1,3], [2,3], [2,1], [3,1], [2,3], [1,2], [1,3], [2,3]



이하 생략

여기서 규칙을 몇개 정도 생각해볼 수 있는데,

• 부분탑의 층수를 하나 늘리기 위해서는 $2^{n-1}$번의 시행이 필요하다
• n층을 완성시키기 위해서는 `n-2층의 과정` + `n-1층의 변형된 과정` + `n-2층의 과정` 이 필요하다

`n-1층의 변형된 과정`이란 다음과 같다.

• n-1층의 과정을 절반으로 나눈다(half_1, half_2)
• half_1의 첫번째를 역전시킨다([1,2] -> [2,1])
• half_2의 첫번째를 역전시킨다
• half_1과 half_2를 이어붙인다

다음의 과정을 따르면, n층을 만드는데 필요한 과정이 도출되므로

n층의 탑을 전체 다 옮기는 데 필요한 과정은 각 층별 소요되는 과정을 모두 합치면 된다.

다른 풀이

위에서 언급한 일반화된 3단계의 과정을 점화식으로 만들어 조금더 Fancy한 코드를 작성할 수도 있다.

 

def solution(n):
    answer = []
# 첫번째 봉(start)에서 두번째 봉(middle)을 사용해 세번째 봉(end)에 n층의 탑을 세우기    
    def hanoi(start, middle, end, n): 
        if n == 1:
            answer.append([start, end])
        else:
# 첫번째 봉(start)에서 세번째 봉을 사용해(end) 두번째 봉(middle)에 n-1층의 탑을 세우기
            hanoi(start,end,middle,n-1) 
# 첫번째 봉에서 세번째 봉으로 마지막 n층을 옮기기
            hanoi(start,middle,end,1) 
# 두번째 봉에서(middle) 첫번째 봉을 사용해(start) 세번째 봉(end)으로 n-1층의 탑을 세우기
            hanoi(middle,start,end,n-1) 
            
    hanoi(1,2,3,n)
    
    return answer

 

P.S : 직관적으로는 이해가 되는 코드이지만, 안의 구동원리까지 완벽히 이해가 되지는 않는다.