하노이의 탑 The Tower of Hanoi

하노이의 탑은 대표적인 재귀함수의 예시이다.

 

세 개의 기둥에 크기가 다른 여러 개의 크기가 다른 원판들이 있고, 처음 기둥에서 다른 기둥으로 모든 원판을 옮기면 된다.

단, 아래의 조건들을 만족해야한다.

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

구현된 코드는 다음과 같다.

#include <stdio.h>

int main(void)
{
	int diskCount;
	printf("Set disk count : ");
	scanf("%d",&diskCount);
	
	hanoi(diskCount,'A','B','C');
}

void move(int diskNum, char from, char to)
{
    printf("\n%d Disk move %c from %c", diskNum, from, to);
}

void hanoi(int n, char from, char by, char to)
{
    if (n == 1)
        move(n, from, to);
    else
    {
        hanoi(n - 1, from, to, by);
        move(n, from, to);
        hanoi(n - 1, by, from, to);
    }
}

1~3의 원반이 있을 때( 숫자가 높을수록 큰 원반 )

 

3번 원반이 C기둥으로 가려면 1, 2번 원반이 B에 있으면 된다.

 

그럼 2번 원반을 우선 B기둥으로 옮겨야 하는데 1번 원반을 C기둥으로 옮기면 된다. 이후 1번 원반을 B기둥으로 옮기면 3번을 제외한 원반들이 B기둥으로 옮겨간다. 그럼 이제 3번 원반을 C기둥으로 옮길 수 있게 된다.

 

그럼 이제 3번을 제외한 원반들을 B에서 C로 옮겨야 하는 상황이 되므로 앞선 메커니즘과 동일하게 B에서 C로 옮겨주면 된다.