[BOJ] 11729 - 하노이 탑 이동 순서

접근

1. 하노이 탑을 1번 장대에서 3번 장대로 옮기는 과정을 출력한다.
2. 원판은 규칙을 지키며 옮겨야 한다.
   ... 한번에 하나씩 옮겨야 하고, 작은 원판은 큰 원판보다 항상 위에 있어야 한다.

재귀 함수를 논할때 흔히 등장하는 예시인 하노이 탑 이동 과정 구하기 문제다. 하지만 나는 지금껏 한번도 풀어보지 않고 있었다
하노이 탑 문제를 (주로) 재귀를 활용하여 푸는 이유는 무엇일까? 다른 이유도 있겠지만 내 생각엔 하노이 탑을 푸는 과정이 점화식 형태로 유도되어 재귀적으로 구현하기 수월하기 때문이 아닐까 싶다.
재귀 구조를 알아보기 위해 손으로 쓰면서 접근해보자. N은 주어진 원반의 수, mov X, Y는 장대 X에 있는 원반을 장대 Y로 옮겨라는 의미이다.

N = 1인 경우

function N_EQUALS_1(from, to, extra):
	mov from, to

N = 2인 경우

function N_EQUALS_2(from, to, extra):
	mov from, extra     -> N_EQUALS_1(from=from, to=extra, extra=to)와 같음
    mov from, to
    mov extra, to       -> N_EQUALS_1(from=extra, to=to, extra=from)와 같음

N = 3인 경우

function N_EQUALS_3(from, to, extra):
	mov from, to        ->
    mov from, extra     -> N_EQUALS_2(from=from, to=extra, extra=to)와 같음
    mov to, extra       -> 

    mov from, to

    mov extra, from     ->
    mov extra, to       -> N_EQUALS_2(from=extra, to=to, extra=from)와 같음
    mov from, to        -> 

이상에서 N = 4인 경우의 이동 과정을 추론해보면 다음과 같을 것이다.

function N_EQUALS_4(from, to, extra):
    N_EQUALS_3(from, extra, to)
    mov from, to
    N_EQUALS_3(extra, to, from)

결국 N개의 원판을 옮기는 하노이 탑 문제는

• 출발지에 있는 N-1개의 원판을 출발지도, 목적지도 아닌 장대로 옮긴 후
• 출발지에 남아있는 원판을 목적지 장대로 옮긴 다음
• 출발지도, 목적지도 아닌 장대에 있는 N-1개의 원판을 목적지로 옮기는

문제로 요약할 수 있는 것이다.
이 과정을 일반화하면

def hanoi(from_, to, extra, count):
    if count == 1:
         print(from_, to)
    hanoi(from_=from_, to=extra, extra=to, count=count - 1)
    print(from_, to)
    hanoi(from_=extra, to=to, extra=from_, count=count - 1)
    

즉, N-1개의 원반에 깔려있는 N번째 원반을 옮기기 위해서는 N-1개의 원반을 출발지도, 목적지도 아닌 다른 곳으로 옮겨두는 것이 선행되어야 하며, N번째 원반을 목적지로 옮긴 다음 다른 곳으로 옮겨두었던 N-1개의 원반을 다시 목적지로 옮기는 과정을 거치는 것이다.
그리고 이것은 규칙으로부터 유도된 풀이법이므로 규칙을 위반하지 않는 이상 이 방법이 최소 이동 횟수를 가지는 방법이 될 수 밖에 없다.

코드 1 - 순진한 구현

from sys import stdin

res = []

def hanoi(from_, extra, to, count):
    global res

    if count == 1:
        res.append((from_, to))
        return

    hanoi(from_=from_, extra=to, to=extra, count=count - 1) # N번째 원반을 옮기기 위해, N-1개의 원반을 피신시킴
    res.append((from_, to)) # N번째 원반을 옮김
    hanoi(from_=extra, extra=from_, to=to, count=count - 1) # 피신...시켜둔 N-1개의 원반을 목적지로 옮김

hanoi(1, 2, 3, int(stdin.readline()))
print(len(res))
for a, b in res:
    print(a, b)

이동 횟수를 구해주기 위해 결과를 바로 출력하지 않고 리스트 res에 결과값을 저장하고 있는데, 이동 과정을 일반화할 수 있으므로 이동 횟수 역시 일반화할 수 있다는 것을 생각해볼 수 있다.
N개의 원반을 이동시킬 때, N-1개의 원반을 두번 이동(from -> extra, extra -> to)하며 N번째 원반은 한 번 이동(from -> to)하므로

와 같이 일반화할 수 있다.

또한 실행 과정을 보면 불필요한 중복이 있다는 것을 알 수 있다. 이를 해결하기 위해 한 번 구했던 값을 기억해두는 다이나믹 프로그래밍 기법을 도입해보자.

코드 2 - 다이나믹 프로그래밍 도입

from sys import stdin

def hanoi(from_, extra, to, count):
    global res

    if count == 1:
        return "%d %d\n" % (from_, to)
    
    if cache[from_][extra][to][count]:
        return cache[from_][extra][to][count]
    
    res = hanoi(from_=from_, extra=to, to=extra, count=count - 1)
    res += "%d %d\n" % (from_, to)
    res += hanoi(from_=extra, extra=from_, to=to, count=count - 1)
    cache[from_][extra][to][count] = res
    return cache[from_][extra][to][count]

N = int(stdin.readline())

sum_ = 1
for i in range(N-1):
    sum_ = sum_ * 2 + 1

cache = [[[["" for _ in range(N + 1)] for _ in range(3 + 1)] for _ in range(3 + 1)] for _ in range(3 + 1)]
print(sum_)
print(hanoi(1, 2, 3, N))

다이나믹 프로그래밍 도입으로 처리 시간이 대폭 줄었다(1224ms -> 76ms). 중간 결과값을 중복하여 저장하지 않아 메모리 사용도 오히려 감소했다.

재귀를 쓰지 않는, 반복문과 배열만으로 하노이 탑을 푸는 방법도 궁금하여 찾아봤으나 제한사항도 있고 덜 직관적이어서 그냥 이정도까지 알아보는 걸로 만족하기로 했다.