Page 181 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

15 int main(void) 실행 결과
16 {
하노이의 탑
17 int n; /* 원반의 개수 */ 원반 개수 : 3
18 printf("하노이의 탑\n원반 개수 : "); 원반[1]을 1 기둥에서 3 기둥으로 옮김
19 scanf("%d", &n); 원반[2]를 1 기둥에서 2 기둥으로 옮김
20 move(n, 1, 3); 원반[1]을 3 기둥에서 2 기둥으로 옮김
원반[3]을 1 기둥에서 3 기둥으로 옮김
21
원반[1]을 2 기둥에서 1 기둥으로 옮김
22 return 0;
원반[2]를 2 기둥에서 3 기둥으로 옮김
23 } 원반[1]을 1 기둥에서 3 기둥으로 옮김

이 프로그램은 기둥 번호를 정수 1, 2, 3으로 나타냅니다. 기둥 번호의 합이 6이므로 시작 기
둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 – x – y로 구할 수 있습니다. 원반은 no개이
므로 move 함수는 아래와 같은 과정을 거칩니다.

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

물론 1 , 3 은 재귀 호출에 의해 해결합니다. no가 3일 때 move 함수의 동작을 그림 5-11에
나타냈습니다.

1 , 3 의 실행은 no가 1보다 큰 경우이므로 그림에서 no가 1인 부분(최하위에 해당하는 부분)에서는 2 만 실행합니다.

move(3, 1, 3) {1,2,3}을 첫 번째 기둥에서 세 번째 기둥으로
1
move(2, 1, 2) {1,2}를 첫 번째 기둥에서 두 번째 기둥으로
1 move(1, 1, 3) {1}을 첫 번째 기둥에서 세 번째 기둥으로
2
원반[1]을 첫 번째 기둥에서 세 번째 기둥으로 옮김
원반[2]를 첫 번째 기둥에서 두 번째 기둥으로 옮김
2
3 move(1, 3, 2) {1}을 세 번째 기둥에서 두 번째 기둥으로
2
원반[1]을 세 번째 기둥에서 두 번째 기둥으로 옮김
원반[3]을 첫 번째 기둥에서 세 번째 기둥으로 옮김
2
3
move(2, 2, 3) {1,2}를 두 번째 기둥에서 세 번째 기둥으로
1 move(1, 2, 1) {1}을 두 번째 기둥에서 첫 번째 기둥으로
원반[1]를 두 번째 기둥에서 첫 번째 기둥으로 옮김
2
원반[2]를 두 번째 기둥에서 세 번째 기둥으로 옮김
2
3 move(1, 1, 3) {1}을 첫 번째 기둥에서 세 번째 기둥으로
원반[1]을 첫 번째 기둥에서 세 번째 기둥으로 옮김
2
[그림 5-11] move 함수의 실행 과정(no = 3일 경우)

05•재귀 알고리즘 181