[Python 문제 풀이] 프로그래머스 '하노이의 탑'

Tower of Hanoi

Recursive method로 풀 수 있는 아주아주 유명한 문제

 

접근

DP 방법으로 접근하여 작은 문제로 분해해야 한다. 디스크는 큰 것이 아래로 가야 하기 때문에 디스크를 옮기다 보면 결국 target pole의 가장 아래에 가장 큰 디스크를 먼저 놓게 될 것이다. N개의 디스크가 있다고 할 때 일반화된 과정은 다음과 같다.

 

1. N-1개의 디스크를 mid pole로 옮긴다.

2. N번 째 디스크를 target pole로 옮긴다.

3. N-1개의 디스크를 target pole로 옮긴다.

*N-1까지의 디스크를 옮길 때에는 source pole, mid pole, target pole이 번갈아가며 바뀐다.

 

위와 같이 큰 하나의 문제가 두 개의 부분문제로 나뉠 수 있고 그것들이 다시 더 작은 문제로 나뉜다. 

 

한편, 재귀 방법의 원리에 의거하여 완벽히 대응되는 비재귀적 방법도 존재한다.

https://www.geeksforgeeks.org/iterative-tower-of-hanoi/

Iterative Tower of Hanoi - GeeksforGeeks

위 사이트에서 관련된 자료를 찾아볼 수 있다. 실제 코드를 살펴보면 매우 길고 복잡한 것을 알 수 있다. 그러나 동작 원리는 완전히 동일하기 때문에 시간복잡도와 공간복잡도는 동일하다고 한다. 

 

하노이의 탑의 recursive 풀이에서는 함수 실행횟수가 double되는 모습을 보이기 때문에 공간복잡도 면에서 비효율적일 것이라 생각했으나 iterative에서도 stack을 사용하기 위해 공간을 사용하고 동일한 수준의 불리함을 가지는 것 같다. 참고로 피보나치 수열을 구하는 문제에서는 함수의 공간복잡도 문제 뿐만 아니라 완전히 동일한 작업을 수행하는 함수의 중복 실행 문제가 있기 때문에 iterative가 더 유리하다.

구현

def solution(n):
    answer = []
    def f(n,src,aux,tar) :
        if n == 1 :
            answer.append([src,tar])
        else :
            f(n-1,src,tar,aux)
            f(1,src,aux,tar)
            f(n-1,aux,src,tar)
    f(n,1,2,3)
    return answer