하노이의 탑 이해하기

 

 

 

 

겉으로 보기에는 하노이의 탑에서 재귀의 조건인 부분 분할의 경우가 없어보이지만, 자세히 들여다 보면 반드시 존재한다.

하노이의 탑은 기둥 3개는 고정이기 때문에 시작점(From), 옮길 지점(To), 나머지 지점(Mid)로 구성된다.

 

 

 

원반 3개 예를 들어보자.(원반을 1에서 3으로 옮기는 과정, N: 3, From: 1, Mid: 2, To: 3)

 

 

 

 

첫번째 빨간 영역은 원반 2개를 (1)에서 (2)로 옮기는 과정이다.(N: 2, From: 1, Mid: 3, To: 2)

이 후, 1->3은 가장 큰 원반을 목적(To)지점으로 옮기는 과정이다.

두번째 빨간 영역은 원반 2개를 (2)에서 (3)로 옮기는 과정이다.(N: 2, From: 2, Mid: 1, To: 3)

 

 

정리하면,

hanoi(3)의 결과는

hanoi(2)를 나머지 지점으로 먼저 옮기고,

가장 큰 원반을 목적지점으로 옮기고,

hanoi(2)를 목적지점으로 옮기는 과정이 된다.

 

이를 일반화 하면

 

hanoi(n)(1,2,3) = hanoi(n-1)(1,3,2) + move(1,3) + hanoi(n-1)(2,1,3) 이 되며

 

 

더 일반화 시켜보겠다.

 

hanoi(n)(From,Mid,To) = hanoi(n-1)(From,To,Mid) + move(From,To) + hanoi(n-1)(Mid,From,To)가 된다.

 

 

코드로 표현하면 다음과 같다.

 

 

    }

void hanoi(int n, int From, int Mid, int To) 
{
    if (n == 1)
        printf("1 : %d -> %d\n", From, To);
    else
    { 
        hanoi(n - 1, From, To, Mid);
        printf("%d : %d -> %d\n", n, From, To);
        hanoi(n - 1, Mid, From, To);
    }
}

}