- 하노이 탑을 1번 장대에서 3번 장대로 옮기는 과정을 출력한다.
- 원판은 규칙을 지키며 옮겨야 한다.
... 한번에 하나씩 옮겨야 하고, 작은 원판은 큰 원판보다 항상 위에 있어야 한다.
재귀 함수를 논할때 흔히 등장하는 예시인 하노이 탑 이동 과정 구하기 문제다. 하지만 나는 지금껏 한번도 풀어보지 않고 있었다
하노이 탑 문제를 (주로) 재귀를 활용하여 푸는 이유는 무엇일까? 다른 이유도 있겠지만 내 생각엔 하노이 탑을 푸는 과정이 점화식 형태로 유도되어 재귀적으로 구현하기 수월하기 때문이 아닐까 싶다.
재귀 구조를 알아보기 위해 손으로 쓰면서 접근해보자. 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개의 원판을 옮기는 하노이 탑 문제는
문제로 요약할 수 있는 것이다.
이 과정을 일반화하면
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개의 원반을 다시 목적지로 옮기는 과정을 거치는 것이다.
그리고 이것은 규칙으로부터 유도된 풀이법이므로 규칙을 위반하지 않는 이상 이 방법이 최소 이동 횟수를 가지는 방법이 될 수 밖에 없다.
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)하므로
와 같이 일반화할 수 있다.
또한 실행 과정을 보면 불필요한 중복이 있다는 것을 알 수 있다. 이를 해결하기 위해 한 번 구했던 값을 기억해두는 다이나믹 프로그래밍 기법을 도입해보자.
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). 중간 결과값을 중복하여 저장하지 않아 메모리 사용도 오히려 감소했다.
재귀를 쓰지 않는, 반복문과 배열만으로 하노이 탑을 푸는 방법도 궁금하여 찾아봤으나 제한사항도 있고 덜 직관적이어서 그냥 이정도까지 알아보는 걸로 만족하기로 했다.