[알고리즘] The Tower of Hanoi

문제

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and
sometimes pluralized as Towers) is a mathematical game or puzzle. It consists of
three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one
rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves
required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

You need to make myHanoi function.

입력

The number of disks. (n >= 1)

출력

The count of movement.
Also, You must print every movement case by case.

예제 입력

7

예제 출력

1 3
1 2
3 2
1 3
2 1
2 3
1 3

주 알고리즘 분류

• 구현
• 재귀
• 분할정복

나만의 풀이

문제를 해결하기에 앞서서, 먼저 이 문제는 내가 과거에 수강했던 컴퓨터 알고리즘 과목의 과제 중 일부임을 밝힌다.
해당 과제를 수행했을 때는 C++을 이용해서 구현했지만, 여기서는 똑같은 문제를 파이썬을 이용해서 구현하려 한다.

그 전에, 먼저 문제부터 간단하게 해석해보자. (영어강의 으악)

감으로 적은 해석본

하노이의 탑이란 게임이 있다. (이후 게임 설명 나오는데 대부분 알 것이므로 생략.)
이 게임의 목적은 한 쪽에 쌓여진 판들을 다른 쪽으로 옮기는 것인데, 다음의 규칙을 따르게 된다.

1. 한 번에 하나의 판만 옮길 것.
2. 판을 옮기는 행위는 판을 들어서 어떤 봉에 놓는 것까지를 의미한다.
3. 크기가 작은 판이 무조건 위에 있어야 한다.

3개의 판이 있으면 7번 움직여야 한다. 하노이의 탑에서 n개의 판이 있음 총 2^n-1회만을 움직여야 한다.

여러분은 myHanoi함수를 만들어야 한다. 입력은 판의 개수 n이며, 출력은 최소로 움직인 판의 횟수와, 각 경우에 따른 판의 이동 과정이다.

오랜만에 문제를 보니까 예전 생각이 난다.
문제 자체도 단순하고, 사실 최종 코드를 보면 엄청 단순할 것이다.

우리가 만들 myHanoi함수는 다음의 구조를 따른다.

def myHanoi(n, _from, _by, _to):
    pass

여기서 n은 현재 (위에서부터) 몇 번째 원판인지, _from은 출발 위치, _to는 판을 놓을 위치, _by는 둘 다 아닌 그냥 빈 위치라 보면 된다.
직관적으로 보면, 그냥 _from에서 _to로 판을 옮긴다 생각하면 되겠다.
더 설명하고 싶지만 아래 전문 코드를 보는게 더 이해가 빠를 것이라 생각한다.

def myHanoi(n, _from, _by, _to):
    global count, rslt  # 전역변수 이용.
    count += 1  # 호출할 때 마다 증가.
    if n == 1:
        rslt.append((_from, _to))
    else:
        myHanoi(n-1, _from, _to, _by)
        rslt.append((_from, _to))
        myHanoi(n-1, _by, _from, _to)

count = 0
rslt = []

n = int(input())

myHanoi(n, 1, 2, 3)

print(count)
for (st, ed) in rslt: print(st, ed)

myHanoi는 재귀적으로 자신을 호출하는데, 크게 2가지 case로 나뉘게 된다.

만일 n=1인 경우, 이때는 그냥 위치 1에서 위치 3으로 판을 옮기면 된다.
따라서 _from에서 _to로 옮긴다는 내용을 저장한다.
그 외의 경우엔 다음과 같이 코드를 짜면 된다.
먼저, n-1번째까지의 판들을 모두 중앙(2번)에 옮겨 놓는다. myHanoi(n-1, _from, _to, _by)
이후 n번째 판은 _from에서 _to로 옮긴다.
마지막으로 남아있는 n-1번째까지의 판들을 중앙(2번)에서 우측(3번)으로 옮긴다. myHanoi(n-1, _by, _from, _to)

맨 처음 보면 아리송한 것 같은데, 하노이 탑 문제를 실제로 (사람이) 푸는 과정을 생각하면 저렇게 풀어야 함을 알 수 있을 것이다.
생각보다 직관적으로 구현 가능한 문제이다.

여담으로 내가 C++로 풀었을 때도 기본 구성은 저 형태와 동일하게 짰다.
다만 중간 결과 저장을 위한 자료구조를 선택하는 과정이 추가로 필요했다.
나는 과거 자료구조 수업때 배웠던 Doubly Linked List를 만들어서 결과를 저장하고 역순으로 출력했었다.
하지만 지금 생각해보니 그냥 vector구조체 썼으면 더 간단하게 만들어지지 않았을까 싶다.
아 맞네 벡터로 .push_back()했음 더 간단했겠네... 괜히 DLL 만들었나