하노이 탑 문제

하노이 탑 문제를 재귀 알고리즘으로 해결합니다.

하노이 탑 문제

하노이 탑은 3개의 기둥에서 원판을 옮기는 과정을 찾는 문제이다. 아래의 글은 백준의 하노이 탑 문제의 설명을 가져온 것이다.

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

• 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
• 이 작업을 수행하는데 필요한 이동 횟수는 최소가 되는 이동 순서를 출력하는 프로그램을 작성하라.

이제 문제를 분석해보자.

문제 분석

하노이 탑 문제에서는 기둥이 3개로 제한된다. 처음에는 C 원판을 3기둥으로 옮겨야 하는데 이를 위해서는 위에 있던 나머지 원판들을 모두 2기둥에 옮겨야 한다. 결국 원판을 목적지까지 옮기면 아래처럼 정리된다.

A ║─  ║   ║   ║       ║   ║   ║   ║       ║   ║   ║   ║       ║   ║   ║   ║       ║   ║   ║   ║    
B ║── ║   ║   ║   ->  ║── ║   ║   ║   ->  ║   ║   ║   ║   ->  ║   ║─  ║   ║   ->  ║   ║─  ║   ║ 
C ║───║   ║   ║       ║───║   ║─  ║       ║───║── ║─  ║       ║───║── ║   ║       ║   ║── ║───║
    1   2   3

• C원판은 B원판이 보관 기둥인 2에 먼저 도착한 후에 도착 기둥인 3으로 이동할 수 있다.
• B원판 위에 있는 A원판이 보관 기둥인 3에 도착한 후에 도착 기둥인 2로 이동할 수 있다.
• A원판은 B원판이 도착하고자 하는 2를 제외한 보관 기둥인 3으로 이동해야 한다.
• B원판은 도착 기둥인 2로 이동하며, B원판이 도착했으므로 A원판도 2로 이동한다.
• B원판이 보관 기둥에 이동한 후에 C원판은 3으로 이동한다.

A ║   ║   ║   ║       ║   ║   ║   ║       ║   ║   ║   ║
B ║   ║─  ║   ║   ->  ║   ║   ║   ║   ->  ║   ║   ║── ║
C ║   ║── ║───║       ║─  ║── ║───║       ║─  ║   ║───║
    1   2   3

• C원판이 도착했으므로 B원판은 보관 기둥 2에서 도착기둥 3으로 이동한다.
• B원판이 이동하기 위해서는 위에 있는 A원판이 보관 기둥인 1로 이동한다.
• B원판이 도착한다.

A ║   ║   ║   ║       ║   ║   ║─  ║
B ║   ║   ║── ║  ->   ║   ║   ║── ║
C ║─  ║   ║───║       ║   ║   ║───║
    1   2   3

• B원판이 도착했으므로 A원판도 도착 기둥인 3으로 이동한다.
• 원판이 하나만 남았을 경우에는 보관이 필요 없이 바로 이동할 수 있다.

이런 구조는 A원판을 제외한 원판마다 출발 -> 경유, 경유 -> 도착 형태의 동일 로직을 사용하고 있음을 보여준다.
또한 각 원판들이 모두 바로 위에 있는 원판의 이동 후에 움직일 수 있다는 규칙도 찾을 수 있다.
이를 로직으로 표현해보자.

1. C(1 -> 3) --- B(1 -> 2) --- 이동(A(1 -> 3))
2.          |             |   이동(B(1 -> 2))
3.          |              --- 이동(A(3 -> 2))
4.          |    이동(C(1 -> 3))
5.           --- B(2 -> 3) --- 이동(A(2 -> 1))
6.                        |    이동(B(2 -> 3))
7.                         --- 이동(A(1 -> 3))

결론적으로 하노이 문제에서 핵심은 크게 3가지로 나눠볼 수 있다.

• 위에 있는 원판을 보관 기둥으로 옯기자
• 그 다음 도착 기둥으로 가자
• 워에 있던 원판을 다시 가져오자.

이제 위 로직을 코드로 작성해보자.

파이썬 코드

아래 함수는 원판의 개수와 출발 기둥, 도착 기둥을 인자 값으로 넣어주면 원판들의 이동 과정을 출력한다.

def hanoi_func(n, _from, _to):
    if n == 0: return 0
    if n == 1:
        print(str(_from)+" "+str(_to))
    else:
        hanoi_func(n-1,_from,6-(_from+_to))
        print(str(_from)+" "+str(_to))
        hanoi_func(n-1,6-(_from+_to),_to)

원판이 1인 경우에는 위에 다른 원판이 없기 때문에 나만 옮겨지면 된다. 그래서 if문으로 예외를 두었다.
나머지의 경우 이전 원판(n-1)을 보관 기둥으로 옮겨주는 과정과 보관 기둥에서 도착 기둥으로 가는 과정을 재귀로 작성하였다.
보관 기둥을 구하는 식은 6-출발기둥-도착기둥인데 그 이유는 간단하다. 기둥이 3개로 한정되어 있고 1+2+3에서 각 기둥을 빼주면 남는 숫자가 보관 기둥이 되기 때문이다.

위 코드는 이동 순서들을 모두 보여주기 때문에 이해하기는 쉽지만, 원판의 개수가 많아질수록 성능이 떨어질 것이다.
만약 이동 순서가 필요없다면 이동 횟수만 수학식으로 구할 수는 없을까?

다행히도 있다. 위에서 찾았던 패턴을 바탕으로 일반항을 구할 수 있다.
어떤 원반의 도착할 때까지의 이동 횟수를 구하려면 다음의 과정이 필요하다.

• $a_{n-1}$: 위(n-1)에 있는 원반이 보관 기둥으로 이동하는 것
• $+1$: 해당 원반이 도착 기둥으로 이동하는 것
• $a_{n-1}$: 위(n-1)에 있는 원반이 도착 기둥으로 이동하는 것

이를 정리하면 아래의 식이 도출된다.

$$a_n = 2a_{n-1}+1$$

위 수식을 정리해서 일반항을 구해보자.

$$a_n+1 = 2(a_{n-1}+1) = 2^{n-1}(a_1+1)$$ $$a_1 = 1 이므로$$ $$a_n+1 = 2^{n}$$ $$a_n = 2^{n}-1$$

이를 파이썬 코드로 작성하면 아래와 같다.

def hanoi_num_func(n):
    if n == 0: return 0
    return 2**n - 1