C언어 재귀적 알고리즘 : 하노이 탑 문제

 

하노이 탑 문제(Hanoi Tower problem)는 재귀적 알고리즘의 전형적인 예

주어진 원반이 세 개의 기둥 중 하나에서 다른 기둥으로 옮기는 최소 횟수를 찾는 것이 목표

각 기둥은 크기가 다른 원반을 수납할 수 있으며, 한 번에 하나의 원반만 다른 기둥으로 옮길 수 있다.

 

 

하노이 탑 문제의 규칙

1. 세 개의 기둥이 있으며, 원반이 하나의 기둥에서 다른 기둥으로 이동해야 한다
2. 한 번에 하나의 원반만 이동할 수 있다
3. 작은 원반이 큰 원반 위에 있을 수 없다
4. B나 C와 같은 중간의 막대를 임시적으로 이용할 수 있으나, 앞의 조건들을 지켜야 한다.

 

 

 

재귀적 알고리즘

 

n개의 원반을 A에서 C로 옮

기는 방법은 다음과 같이 정의:

1. n-1개의 원반을 A에서 B로 옮김
2. 남은 가장 큰 원반을 A에서 C로 옮김
3. B에 있는 n-1개의 원반을 C로 옮김

 

// 막대 from에 쌓여있는 n개의 원판을 막대 tmp를 사용하여 막대 to로 옮긴다

#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;
}