[03]C언어 재귀- 하노이 타워(The tower of hanoi)

• 하노이 타워 문제의 이해

하노이 타워란 ?

하나의 막대에 쌓여있는 원반을 다른 하나의 원반에 그 모양 그대로 옮겨라!

이때, 원반은 한 번에 하나씩만 옮길 수 있고,

'그 모양 그대로' ! 즉, 가장 아래에는 가장 큰 원반에서 시작해서 갈수록 크기가 작아져야 합니다.

 

• 하노이 타워 문제를 직접 그려보자! 

 EX)원반이 3개있을 때 막대 B를 경유하여 막대 A → C 로 원반을 옮겨보자

1. 1번째 원반은 도착점 C로 옮긴다.

2. 2번째 원반은 경유할 B로 옮긴다.

3. C에 있던 1번째 원반을 B로 옮긴다.

4. 출발점 A에 있던 3번째 원반을 도착점 C로 옮긴다.

5. 경유점 B에 있던 1번째 원반을 A로 옮긴다.

6. 경유점 B에 있던 2번째 원반을 C로 옮긴다.

7. 마지막 원반을 도착점 C로 옮기면 완성!

• 하노이 타워 문제의 핵심 - 재귀적인( 반복적인 ) 패턴을 알아보자.

위 그림에서 본 과정 중 핵심만을 정리해보도록 하겠습니다!

일단, A → C 로 가기 위해서는 B의 도움을 받아야합니다. 따라서,

1. A에 있던 원반 중에 가장 큰 원반을 제외한 나머지 원반 ( 그림에서는 1,2 번째 원반 ) 을 B에 놓고

2. A에 있던 가장 큰 원반을 도착점 C에 놓고

3. B에 있던 나머지 원반들을 도착점 C에 옮긴다.

이 세가지 과정이 하노이 타워의 큰 재귀적 흐름인데요.

그런데 여기서 뭔가 찜찜하지 않으신가요?

그림에서 볼 수 있듯이, 밑줄 친 3번과정에서 B에 있는 원반은 2개입니다.

따라서 B에 있는 원반을 한번에 C로 옮길 수 없으므로 부가적인 과정이 필요한데,

왜 이 과정은 써있지 않을까요?

답은 , B에 있는 원반을 C로 옮기는 과정은 원반의 갯수만 2개로 줄여서 다시 재귀반복문을 호출하면 되기 때문입니다.

그래서 이걸 바로 '재귀적 흐름' 이라고 부르는 거죠!

이제 원반 3개 대신 원반 n개를 옮기는 과정으로 일반화 시켜 보겠습니다.

1. 가장 아래원반을 제외한 나머지 원반 n-1 개를  A → B로 이동

2. 가장 아래원반 n번째 원반을 A → C로 이동

3. 나머지 원반 n-1 개를 B → C로 이동

• 하노이 타워 c언어 코드

재귀함수에서는 재귀를 나갈 수 있는 "탈출 조건"이 중요해요 !

탈출 조건이 있어야만 무한루프를 돌지않습니다.

하노이 타워 문제의 탈출 조건은

이동해야 할 원반의 수가 1개일 때 입니다.

n이 1 이면 따로 재귀적인 반복문 필요 없이 A → C로 옮기면 되니까요.

따라서 탈출 조건은

#include <stdio.h>
 
if (num == 1){ // num = 원반의 갯수
    printf("%d번째 원반을 %c 에서 %c 로 이동\n", num,from, to);
}

이 되겠네요.

이제 탈출하지않고 재귀함수를 빙빙돌때 코드만 작성하면 되는데요.

위에 우리가 정리해놨던 재귀의 흐름 !

1. 가장 아래원반을 제외한 나머지 원반 n-1 개를  A → B로 이동

2. 가장 아래원반 n번째 원반을 A → C로 이동

3. 나머지 원반 n-1 개를 B → C로 이동

이 흐름을 그대로 코드로 옮기기만 하면 됩니다.

정리된 코드는 아래에 올려놓았습니다. 

#include <stdio.h>
 
 
void Hanoi(int num, char from, char by, char to)
{
    if (num == 1)
    {
        printf("%d번째 원반을 %c 에서 %c 로 이동\n", num,from, to);
    }
    else
    {
        Hanoi(num - 1, from, to, by); 
        printf("%d번째 원반을 %c에서 %c로 이동\n", num, from, to);
        Hanoi(num - 1, by, from, to);
    }
}
void main()
{
    Hanoi(3, 'A', 'B', 'C');
}