3.2.2 하노이 타워 알고리즘 구현

하노이 타워 알고리즘을 구현합시다. 알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다.

 

만약 돌이 없으면 아무 것도 수행하지 않고 함수를 종료합니다. 즉 탈출 조건입니다.

 

먼저 src에 있는 n-1개의 돌을 dest를 이용하여 use로 옮깁니다. 이 때 재귀로 호출합니다.

 

그리고 src에 있는 돌을 dest로 옮깁니다.

 

마지막으로 use에 있는 n-1개의 돌을 src를 이용하여 dest로 옮깁니다.

 

다음처럼 간단하게 테스트 코드를 작성하여 확인해 보세요.

 

다음은 하노이 타워 알고리즘을 실행했을 때 화면입니다.

[그림 3.3] 하노이 타워 실행 화면

[그림 3.3] 하노이 타워 실행 화면

 

수행 속도를 확인하기 위해 다음과 같이 테스트 코드를 수정해서 확인해 보면 단지 2개의 돌을 늘렸는데 수행 시간은 앾 4배 증가하는 것을 볼 수 있습니다.

[그림 3.4] 하노이 타워 수행 속도 비교 화면

[그림 3.4] 하노이 타워 수행 속도 비교 화면