하노이의 탑

지난 글 : [알고리즘/Do it 알고리즘] - 재귀 알고리즘 분석

 

하노이의 탑 알아보기

하노이이 탑(towers of Hanoi)은 큰 원반이 아래에, 작은 원반이 위에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제다. 모든 원반의 크기가 다르고 처음에는 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

 

일렬로 나열된 3개의 기둥이 있다. 이 중 첫 번째 기둥에 원반 3개가 규칙에 맞게 쌓여 있고, 이를 세 번째 기둥으로 옮기려 한다. 처음 원반이 놓인 기둥을 '시작 기둥', 목적지 기둥을 '목표 기둥', 중간에 있는 기둥을 '중간 기둥이라 부르자. 원반은 가장 작은 원반을 원반 1, 가장 큰 원반을 원반 3, 중간 크기의 원반을 원반 2라 한다.

 

원반이 3개일 때, 원반 1과 원반 2가 겹친 것을 '그룹'이라 부르자. 모든 원반을 최소의 단계로 목표 기둥으로 옮기려면 아래와 같이 3단계로 나눌 수 있다.

1. '그룹'을 시작 기둥에서 중간 기둥으로 옮긴다.
2. 원반 3(가장 큰, 아래에 있는 원반)을 시작 기둥에서 목표 기둥으로 옮긴다.
3. '그룹'을 중간 기둥에서 목표 기둥으로 옮긴다.

 

아래는 하노이의 탑을 구현하는 프로그램이다. move 메서드의 매개변수 no는 옮겨야 할 원반의 개수, x는 시작 기둥의 번호, y는 목표 기둥의 번호다.

출력 결과

이 프로그램은 기둥 번호를 정수 1, 2, 3으로 나타낸다. 기둥 번호의 합이 6이므로 시작 시둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x - y로 구할 수 있다. move 메서드는 no개의 원반을 아채와 같이 3단계에 걸쳐 옮긴다.

1. 바닥의 원반을 제외한 그룹(원반[1]~원반[no - 1])을 시작 기둥에서 중간 기둥으로 옮긴다.
2. 바닥의 원반 no를 시작 시둥에서 목표 기둥으로 옮겼음을 출력한다.
3. 바닥의 원반을 제외한 그룹(원반[1]~원반[no - 1])을 중간 기둥에서 목표 기둥으로 옮긴다.

 

하노이의 탑을 프로그램으로 구현하고 이해하기까지 약 10분 정도 걸린 것 같다. 그저 따라서 작성할 때와 이해하고 바라보는 코드는 정말 다른 느낌이다. 하노이의 탑도 처음에는 어려웠지만 프로그램의 실행 순서나 방법 등을 확실히 알고 가는 것이 중요한 것 같다. 

 

참고 서적 :