3하노이의 탑 알고리즘

 

자, 원반 n개를 옮기는 경우까지 모두 이해가 되나요? 하노이의 탑 옮기기 알고리즘을 자세히 적어 보면 다음과 같습니다.

 

1-A | 원반이 한 개면 그냥 옮기면 끝입니다(종료 조건).

1-B | 원반이 n개일 때

➊ 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮깁니다(3번 기둥을 보조 기둥으로 사용).

➋ 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.

➌ 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮깁니다(1번 기둥을 보조 기둥으로 사용).

 

원반이 한 개일 때가 바로 ‘종료 조건’에 해당합니다. 원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 하는데, 이는 바로 ‘좀 더 작은 값으로 자기 자신을 호출’하는 과정입니다. 따라서 이 문제는 전형적인 재귀 호출 알고리즘에 해당합니다.

다음으로 프로그램 6-1을 볼까요?