[dovelet][재귀] 하노이 탑 (hanoi)

dovelet    9 단계 재귀

하노이 탑 (hanoi)

http://59.23.113.171/30stair/hanoi/hanoi.php?pname=hanoi

#include <stdio.h>
 
void hanoi(int n, int x, int y, int z)
{
    if (n > 0){
        hanoi(n - 1, x, z, y);
 
        printf("%d -> %d\n", x, z);
 
        hanoi(n - 1, y, x, z);
    }
}
 
int main(void)
{
    int n;
 
    scanf("%d", &n);
 
    hanoi(n, 1, 2, 3);
 
    return 0;
}

단순히  이동 횟수를 묻는 거라면 2*f(n-1)+1을 재귀로 돌리면 됨

이동 경로를 나타내는 문제인데

제공된 기본 소스에서 그저 n을 입력받고 넣는 거 밖에 추가하지 않음

hanoi 함수에서 처음 처음 호출되는 부분은 맨 위의 블럭으로 가기 까지 호출하고

맨 위 블럭인 n = 1이 되었을 때 부터 print문으로 다시 돌아오면서 출력

예를 들어서 n = 3일 때   3에서 1로 먼저 간다음에

 1번 블럭을 1->3

 2번 블럭을 1->2

2였을 때 출력하고 나서 밑에 있는 재귀문을 통해 n = 1 

다시 1번 블럭을 3->2

돌아와서 n이 3이었을 때 자기가 1->3이동하고

밑에 재귀를 통해서 2번 블럭으로가고

다시 1번 블록으로 가서 2->1

     2번 블럭을 2->3

     1번 블럭을 1->3

처음에 재귀를 해석할 때에는 몰랐는데

지금 생각하면서 쓰니까

그래프가 머릿속으로 그려진다

3

  2      2 

     1   1  1   1

  .... 그리니까 별거 아닌거처럼 보이네..

뭐 아무튼 이것도 dfs 같이 그래프를 그리고 탐색하는 거 같이 느껴진다

블럭은 그렇다 치고

x y z 는  이동 할 때마다 위의 함수는 x 에서 y 또는 z 로 이동하는 거

   밑의 함수는 y 에서 x 또는 z 로 이동하기 때문