[Data Structure] 하노이 타워 문제 해결

하노이 타워 문제 해결 알고리즘

"원반은 한 번에 하나씩만 옮길 수 있습니다. 그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안됩니다."

 

 

다음과 같은 제약조건을 만족시키기 위해 막대가 두 개가 아닌 세 개가 존재해야 한다.

 

 

하노이 타워 문제의 해결

 

막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성이 된다.

 

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

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

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

 

위의 결론을 코드로 옮겨보면, 

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	. . . .
}

또한, 재귀함수를 정의하는데 있어서 반드시 생각해야 할 것은 재귀의 탈출조건이다.

 

탈출의 조건은 "이동해야 할 원반의 수가 1개인 경우!" 라고 할 수 있다.

 

이동해야 할 원반의 수가 1개이면 그냥 옮기면 그만 아닌가? 그래서 이것이 탈출의 조건이 된다.

그럼 함수에 탈출조건을 반영해보겠다.

 

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to)
{
	if(num == 1) // 이동할 원반의 수가 1개라면
    {
    	printf("원반1을 %c에서 %c로 이동 \n", from, to);
    }
    else
    {
    	. . . .
    }
}

 

이제 원반 n개를 막대 C로 옮기는 세 개의 과정에 해당하는 코드를 추가하여 코드를 완성해보자. 

 

#include <stdio.h>

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
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);                       // 3단계 중 1단계
        printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);   // 3단계 중 2단계
        HanoiTowerMove(num - 1, by, from, to);                       // 3단계 중 3단계
    }
}

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

 

 

실행 결과 (원반 3개, A->C 이동)

 

실행 결과 (원반 4개, A->C 이동)