CODICT
하노이의 탑 옮기기 본문
하노이의 탑(Tower of Hanoi)은 원반을 옮기는 간단한 퍼즐이다. 규칙을 설명하자면, 하노이의 탑에는 크기가 다른 원반이 n개가 존재하고 원반을 끼울 수 있는 기둥에 3개 존재한다. 하노이의 탑 문제는 어떻게 하면 원반 n개를 모두 가장 왼쪽 기둥에서 가장 오른쪽 기둥으로 옮길 수 있을지에 대한 답을 구하는 문제이다.
단 원반을 옮길 때는 3개의 조건이 존재한다. 원반은 한 번에 한 개만 옮길 수 있고, 각 기둥의 맨위의 원반을 다른 기둥의 맨 위로만 옮겨야 하고, 옮기는 과정에서 큰 원바을 작은 원반 위에 올려서는 안된다. 이 규칙을 지키면서 원반을 옮기려면 중간에 여분으로 주어진 보조 기둥을 활용해야 한다.
풀어보기
원반이 한 개일 때
1번 기둥에 있는 원반을 3번 기둥으로 옮기면 끝이다.
한 번에 원하는 곳으로 원반을 옮겼다.
원반이 두 개일 때
- 1번 기둥의 맨 위에 있는 원반을 2번 기둥으로 옮긴다.
- 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮긴다.
- 2번 기둥에 남아 있는 원반을 3번 기둥으로 옮긴다.
세 번 만에 원반 2개를 원하는 곳으로 옮겼다.
원반이 세 개일 때
원반이 세 개일 때부터는 조금 생각이 필요하다. 여기서부터는 원반이 두 개인 문제를 이미 풀었다는 사실을 기억해야한다. 그러니까, 우리는 특정 기둥에 있는 원반 두 개를 우리가 원하는 기둥으로 옮기는 방법을 이미 알고 것이다.
- 1번 기둥에 있는 원반 3개 중 위에 있는 원반 두 개를 비어 있는 2번 기둥으로 옮긴다. 하노이의 탑 규칙에 따르면 한 번에 원반을 두 개씩 옮길 수는 없지만, 이미 원반이 두 개일 때 하노이의 탑을 푸는 방법을 알고 있으니 그 방법을 따라서 하면 된다. 3번 기둥을 보조 기둥으로 생각하면 된다.
- 1번 기둥에 남아 있는 큰 원반을 3번 기둥으로 옮긴다.
- 2번 기둥에 있는 원반 두 개를 3번 기둥으로 옮긴다. 비어 있는 1번 기둥을 보조 기둥으로 활용하여 2번 기둥에 있는 원반 두 개를 3번 기둥으로 옮기는 것이다.
정리하면 원반을 한 개씩 전부 7번 옮기면 문제가 해결된다. 그럼 일반화를 시켜보겠습니다.
원반이 n개일 때
- 1번 기둥에 있는 n-1개의 원반을 2번 기둥으로 옮긴다.
- 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옴긴다.
- 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 옮긴다.
보조 기둥이 바뀔 뿐, 전체적인 움직임에는 큰 차이가 없다.
하노이의 탑 알고리즘
이제 일반화한 경우까지 다 이해를 했다고 가정하고, 알고리즘을 자세히 적어보겠습니다.
- 원반이 한 개면 그냥 옮기면 된다.
- 원반이 n개일 때
- 1번 기둥에 있는 n개의 원반 중 n-1개를 2번 기둥으로 옮긴다.
- 1번 기둥에 남은 가장 큰 원반을 3번 기둥으로 옮긴다.
- 2번 기둥에 있는 n-1개의 원반을 3번 기둥으로 옮긴다.
원반이 1개일 때가 바로 종료 조건에 해당되는 것이다. 원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 하는데, 이는 바로 좀 더 작은 값으로 자기 자신을 호출하는 과정이다. 재귀 호출 알고리즘에 해당하는 문제라는 뜻이다. 그럼 이제 코딩을 해보자.
def hanoi(n, start = 1, goal = 3, use = 2):
if n == 1: # 원반 1개를 옮기는 문제는 그냥 옮기면 됩니다.
print("[+]", start, "to", goal)
return
hanoi(n - 1, start, goal, use) # 원반 n - 1개를 goal를 보조기둥으로 삼아 use로 이동합니다.
print("[+]", start, "to", goal) # 가장 큰 원반을 goal로 이동합니다.
hanoi(n - 1, use, goal, start) # use에 있는 원반 n - 1개를 goal로 이동합니다.
while True:
count = 0
command = int(input("Please enter the command: "))
if command == 0:
break
hanoi(command)
print("[+] Solve.")출력은 이렇습니다.
알고리즘 분석
프로그램 실행 결과를 바탕으로 알고르즘을 분석해보면, 탑의 층수가 높을 수록 원반을 더 많이 움직여야 한다. 위에는 안 나왔지만, 4층이면 15번, 5층이면 31번을 움직여야 한다.
그럼 n층자리 하노이 탑을 옮기려면 원반을 몇 번 움직여야 할까? n층짜리 하노이탑을 올기려면 원반을 총 $$2^n - 1$$번 옮겨야 한다. n이 커지면 -1은 의미가 없으니, $$O(2^n)$$으로 표현할 수 있다. 이는 2를 n번 제곱한 값이니 n이 커짐에 따라 값이 기하급수적으로 증가한다. 원반 하나 옮기는데 1초가 걸린다고 하면, 20층짜리 하노이 탑 문제 푸는데 12일이 넘게 걸린다. 30층짜리면 34년 동안 숨만 쉬도 원반만 옮겨야 한다. 하노이 탑은 적당히 10개 미만으로나 하자.