2.4 하노이탑 문제 출력값을 분석해보자!

The Tower of Hanoi

 

[조건]

• 한 번에 하나의 원판만 이동 가능
• 맨 위에 있는 원판만 이동 가능
• 크기가 작은 원판 위에 큰 원판을 쌓는 것 불가능
• 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 함

 

[코드]

#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to){
    if(n==1) printf("원판 1을 %c에서 %c으로 옮긴다. \n", from, to);
    else {
        hanoi_tower(n-1, from, to, tmp);
        printf("원판 %d을 %c에서 %c으로 옮긴다. \n", n, from, to);
        hanoi_tower(n-1, tmp, from, to);
    }
}
int main(void){
    hanoi_tower(4, 'A', 'B', 'C');
    return 0;
}

 

[출력값]

 

[분석]

순환함수를 이용해 문제의 크기를 계속 줄여나가는 방식이다.