어느 덧 책에서 재귀라는 단어가 나오게 되었습니다.
재귀라는 것은 전에 포스팅한 글 보다 잘쓰기가 힘들거 같아서
설명은 링크로 하고... 하노이 탑에 대해서 설명해볼까합니다.
재귀호출에 대한 설명 글 보기!
자 그럼 S t A r T !!
------------------------------------------------------------
하노이 탑에 대해서 일단 설명 해보겠습니다.
위 그림에서 원판이 있는 막대를 A 중앙을 B 가장 왼쪽을 C 막대로 지칭하도록 하겠습니다.
일단, 목표는 간단합니다. A막대에서 C막대로 모든 원판을 크기 순서대로 옮기면 됩니다.
이때 제약 사항이있죠~
ⓐ 한번에 하나의 원판만 이동 가능!!
ⓑ 맨 위에 있는 원판만 이동 가능!!
ⓒ 크기가 작은 원판 위에 큰 원판이 있을 수 없음!! ( 무조건 옮긴 원판의 아래에는 더큰 우너판 이있어야 한다!)
ⓓ 중간 막대를 이용시에도 위의 3가지 조건을 만족해야한다~
재귀적 관점에서 한번 문제를 접근해보도록 하자
재귀적 방법으로 접근한 알고르짐은 다음과 같다
ⓐ A의 원판에 맨 아래 있는 원판을 제외하고 B로 옮긴다.
ⓑ A원판에 남아 있는 것을 C로 옮긴다.
ⓒ B원판에 맨 아래 있는 원판을 제외하고 A로 옮긴다.
ⓓ B원판에 남아 있는 것을 C로 옮긴다.
ⓔ A와 B에 원판이 모두 없을 때까지 ⓐ~ⓓ까지 모든 과정을 반복한다.
위의 알고리즘을 의사코드로 정리하면
void hanoi_T(int n, char from, char to, char temp){
// n : 원판의 개수 / from : 옮겨야 할 원판 이 있는 곳 / to : 원판을 옮길 곳 / temp : 남은 막대
if ( n == 1 ) { // 원판이 하나 남았을 경우
from 에서 to로 이동
}else{
맨 밑에 원판을 제외한 나머지 원판을 temp로 옮긴다. // 재귀적 호출
맨 밑의 원판을 to로 옮긴다.
temp의 원판을 to로 옮긴다. // 재귀적 호출
}
}
약간 이해가 안될지도 모르지만... 3개짜리 원판을 놓고선 한번 위의 의사코드처럼 움직이다보면
'아하! 이런거구나' 깨달음이...
소스를 작성해보면....
#include<stdio.h>
void hanoi_T(int n, char from, char temp, char to){
if ( n == 1 ){
printf("원판 1 / %c -> %c\n",from,to); // ⓑ,ⓓ의 단계에 해당하죠~
}else{
hanoi_T( n-1, from, to, temp); // 파라매터 순서를 보세요 ⓐ단계에 해당하죠~
printf("원판 %d / %c -> %c\n",n,from,to); // ⓐ, ⓒ단계를 하면서 이동하는 것을 나타내죠~
hanoi_T(n-1, temp, from, to); // 파라매터 순서를 보세요 ⓒ단계에 해당하죠~
}
}
void main(){
char from = 'A';
char temp = 'B';
char to = 'C';
int num;
printf("원판 개수를 선택해주세요 : ");
scanf("%d",&num);
hanoi_T(num, from, temp, to);
}
------------------------------------------------------------------
이것으로 간단하게 재귀를 넘기고 다음엔 트리로 넘어가도록하죠~