하노이 타워
-
5. The Tower Of Hanoi ( 하노이 타워 )C 자료구조/1. 재귀함수 2020. 6. 10. 10:26
원반이 3개인 경우의 그림부터 보자. 가장 작은 원반을 1번, 가장 큰 원반을 3번이라고 하자. [그림 1 : 3개의 원반을 가지는 하노이의 탑 문제 ] 위의 그림에서 원반의 이동의 순서를 알아보도록 하자. 각 이동단계는 아래의 그림들과 같다. [ 그림 Step 1 ] [ 그림 Step 2 ] [ 그림 Step 4 ] [ 그림 Step 5 ] [ 그림 Step 6 ] [ 그림 Step 7 ] 위 그림을 통해 알 수 있는 규칙은 아래와 같다. 이 규칙은 원반이 4개인 경우에 대해서도 성립한다. 1. A막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 B로 이동시킨다. 2. 그리고 나서 가장 큰 원반인 3번 원반을 막대기 C로 이동시킨다. 3. B 막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 C로 이동..