🍒 재귀 (Recursion) (2)

📌 하노이 타워 : The Towe of Hanoi

하노이 타워는 재귀 함수의 강력함을 보여주는 대표적인 예로 꼽힙니다.

 

하노이 타워

모르는 사람을 위해 간략하게 설명하자면,

 

세 개의 기둥(A, B, C)과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다.

게임의 목적은 다음 세 가지 조건을 만족시키면서, 한 기둥(A)에 꽂힌 원판들을 그 순서 그대로 다른 기둥(C)으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

위 그림 처럼 세 개의 원판만을 사용하여 옮기는 것은 크게 어렵지는 않습니다.

일단 3번 원판 (제일 큰 원판)을 밑에다 쌓으려고 보니, 1번과 2번 원판 때문에 불가능합니다.

그래서 이 1,2 번 원판을 먼저 B기둥에다가 쌓아 놓으면 3번 원판을 C기둥으로 가져다 놓을 수 있습니다.

 

그렇다면

 

(1, 2, 3) 원판을 옮기려면, (1, 2) 원판 먼저 다른 기둥으로 옮겨 놓아야 한다.

 

는 생각을 하게 됩니다.

그렇다면 원판 4개로 시작한다면 어떨까요?

 

제일 큰 원판 (4 번째 원판)을 옮기려면 먼저 그 위에 있는 1, 2, 3 원판을 B에 옮겨놓아야 하겠죠?

그래야 4번째 원판을 C로 옮길 수 있습니다.

원판 1, 2, 3 을 B 기둥에 옮기는 방법은 방금 같이 살펴본 그림에 나와있습니다. 

 

결론적으로,

👉 n개의 원판을 옮기려면, 먼저 n-1개의 원판을 다른 기둥으로 옮겨놓아야 한다.👈

 

함수를 작성하기에 앞서 좀 더 세분화해서 적어보자면,

 

1. 작은 원판 n-1개를 (맨 아래의 원판을 제외한 나머지 원판을) A에서 B로 이동

2. 큰 원판(맨 아래의 원판) 1개를 A에서 C로 이동

3. 작은 원판 (위의 1단계에서 옮겨진 원판) n-1개를 B에서 C로 이동

 

 코드 작성을 시작해볼게요.

 

void HanoiTowerMove(int num, char from, char by, char to)
{
    
}

먼저 함수를 선언합니다.

위 함수의 매개변수 선언이 의미하는 바는

 

👉 "num개의 원판을 by를 거쳐 from에서 to로 이동한다." 👈

 

그렇다면 재귀 함수 정의에서 가장 중요한 탈출 조건은 어떻게 될까?

 

이동해야 할 원판의 수가 1개의 경우가 탈출 조건이 되겠죠? 

void HanoiTowerMove(int num, char from, char by, char to) {
    if (num == 1) //이동할 원판의 개수가 1개라면
    {
        printf("원판 1을 %c에서 %c로 이동 \n", from, to);
    } else {
    
    }
}

탈출 조건을 추가한 코드입니다.

재귀 함수를 호출하지 않고 출력만 합니다!

 

그럼 이번에는 세분화 단계에서 적은 첫 번째 단계,

 

1. 작은 원판 n-1개를 (맨 아래의 원판을 제외한 나머지 원판을) A에서 B로 이동

 

이 부분을 코드에 추가해볼게요.

void HanoiTowerMove(int num, char from, char by, char to) {
    if (num == 1) //이동할 원판의 개수가 1개라면
    {
        printf("원판 1을 %c에서 %c로 이동 \n", from, to);
    } else {
        HanoiTowerMove(num - 1, from, to, by);
    }
}

else 부분을 보면, 인자로 전달된 to가 by로 전달되고, by가 to로 전달되고 있습니다.

왜냐하면 num 개의 원판을 A에서 C로 옮기려면, 먼저 num-1개의 원판을 A에서 B로 옮겨야 하기 때문입니다.

 

그럼 이제 

 

2. 큰 원판(맨 아래의 원판) 1개를 A에서 C로 이동

3. 작은 원판 (위의 1단계에서 옮겨진 원판) n-1개를 B에서 C로 이동

 

이 부분을 코드에 추가해볼게요.

void HanoiTowerMove(int num, char from, char by, char to) {
    if (num == 1) //이동할 원판의 개수가 1개라면
    {
        printf("원판 1을 %c에서 %c로 이동 \n", from, to);
    } else {
        HanoiTowerMove(num - 1, from, to, by);
        printf("원판 %d을 %c에서 %c로 이동 \n", num, from, to);
        HanoiTowerMove(num - 1, by, from, to);
    }
}

하노이 타워의 문제를 해결하는 재귀 함수가 완성 되었습니다.

 

한 번 예제로 테스트를 해볼까요?

 

int main (void)
{
    // 막대 A의 원판 3개를 막대 B를 경유하여 막대 C로 옮기기
    HanoiTowerMove(3,'A','B','C');
    return 0;
}

실행 결과

성공적입니다.