하노이의 탑 이해하기

 

 

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

하노이의 탑은 기둥 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);
    }
}

}