재귀 하노이탑

2019.01.04.

 

하노이탑은 막대 3개가 있고 크기가 다른 원 N개 가 있다.

반지름이 작은우너은 항상 반지름이 자신보다 큰원보다 위에있어야 된다.

이 규칙에 따라 막대 하나에 크기가 다른 원 3개를 껴놓고 다른 막대로 모든 원을 옮기는 것이다.

 

ex)

 

A,B,C라는 막대에 반지름 1,2,3인 3개의 원이 있을때 과정이다.

 

A    B    C

1

2

3

 

A    B    C

3    2    1

 

A    B    C

3    1    

2

 

A    B    C

1    3

2

 

A    B    C

1          2

3

 

A    B    C

1

2

3

 

다음과 같이 진행될때 만약 원이 4개가 있으면 어떻게 될까?

 

ex)

A    B    C

1

2

3

4

 

A    B    C

4    1

2    

3

 

A    B    C

1    4

2

3    

 

A    B    C

1

2

3

4

 

위와 같이 된다. 123을 이동하는 방법은 위에 언급한 방법과 같기 때문에

반복되는 부분이 생긴다.

 

1)작은원반 N-1개 A=>B

2)큰원반 1개 A=>C

3)작은 원반 N-1개 B=>C

 

이에 따라 코드를 짜보면

 

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

 

 

참고: 윤성우의 열혈 자료구조