하노이 타워

하노이 타워 문제의 이해

하노이 타워 : 원반은 한번에 하나씩 옮길 수 있으며 옮기는 과정에서 작은원반위에 큰 원반이 올라가서는 안된다.

 

원반의 수가 많아질수록 하노이 타워의 문제해결이 어려워진다. 그러나 하노이 타워도 원반의 수가 늘어날 수록 일련의 과정을 더 많이 반복할 뿐이다.

 

하노이 타워 문제의 해결

막대 A,B,C가 있을 때, 막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성이 된다.

1.작은 원반 n-1개를(가장 큰 맨 아래 원반을 제외한 나머지 원반)A에서 B로 이동

2.큰 원반(맨 아래의 원반) 1개를 A에서 C로 이동

3.작은 원반(가장 큰 원반 제외) n-1개를 B에서 C로 이동.

 

위를 재귀로 구성할 때 탈출 조건은 "이동해야할 원반의 수가 1개"인 경우이다. 이동해야할 원반의 수가 1개이면 그냥 옮기면 되기 때문이다.

 

하노이 타워 함수

하노이 타워 함수

위 함수의 매개변수 from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동한다는 의미의 변수들이다.

 

HanoiTowerMove(num-1, from, to, by);

위 함수는 n-1개의 원반을 A에서 B로 이동하는 함수이다. 이후 printf()함수를 통해 가장 큰 원반(맨 아래의 원반)1개를 A에서 C로 이동한다.

HanoiTowerMove(num-1, by, from, to);함수를 통해 B에 있는 n-1개의 원반을 C로 이동시킨다.

 

하노이 타워 원반 3개

 

출력결과