[자료구조] 재귀(순환)함수 recursion - 하노이 탑

1. 재귀란?

함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.

 

재귀 참고 링크 :

https://coding-ok.tistory.com/7?category=1011888

[자료구조] 재귀(순환)함수 recursion

 

2. 하노이 탑

하노이 탑은 크기가 다른 3개의 원판을 옮기는 문제이다.

원판이 n개 있다고 한다면 이를 재귀로 해결할 수 있다.

 

먼저 n개의 원판을 생각하지 말고 2개의 원판만 있다고 생각해보자.

2개의 원판이 A(출발지)에 있다고 생각하고

위의 원판을 B(중간 기둥)에 옮기고

아래 원판을 C(목적지)에 옮기고

B(중간 기둥)에 있던 원판을 C(목적지)위에 올리면 모두 이동할 수 있다.

 

n개의 원판이 있다고 생각해본다면

n개의 원판이 A에 쌓여있을 때,

가장 먼저 위에 있는 n-1개의 원판을 B로 옮긴 후

남아있는 1개의 원판을 C로 옮긴다.

그리고 B에 있는 n-1개의 원판을 C 위에 올린다.

 

//from 기둥에 있는 n개의 원판을 to 기둥으로 옮긴다.
//즉 from은 출발지, temp는 (목적지가 아닌) 중간 기둥, to는 최종적으로 원판을 놓고 싶은 기둥이다.

void hanoi(int n, char from, char temp, char to){
    if(n == 1){
        //from에 있는 1개의 원판을 to로 옮긴다.
        printf("원판 1개를 %c에서 %c로 옮긴다.", from, to);
        
    }else{
        //from의 맨 밑의 원판을 제외한 나머지 원판들을 temp로 옮긴다.
        hanoi(n-1, from, to, temp);
        //from에 있는 한개의 원판을 to로 옮긴다.
        printf("%d를 %c에서 %c로 옮긴다.", n-1, from, to);
        //temp의 원판들을 to로 옮긴다.
        hanoi(n-1, temp, from, to);
    }
}

int main(int argc, const char * argv[]) {
    hanoi(3, 'A', 'B', 'C');
}