순환 알고리즘입니다.
코드는 다음과 같습니다.
void hanoi_tower(int n, char from, char tmp, char to){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
void main(){
int disk = 5;
hanoi_tower(disk, 'A', 'B', 'C');
}
>[추가 설명] : PC 모니터로 보셔야 코드를 한줄한줄 보시기 편합니다.
이제 다음의 설명을 이어가기에 앞서서,
어떻게 코드가 전개되는지 살펴보도록 하겠습니다.
5개의 원판의 이동보다 3개의 원판의 이동하는 횟수가 적어서 한눈에 보기 편하기 때문에,
원판이 3개일 때의 이동 방법을 코드를 통해 살펴보겠습니다.
배경색이 회색으로 되어있는 부분이 조건절 if-else 문에서 선택되어 실행된 코드입니다.
void main(){
int disk = 3;
hanoi_tower(disk, 'A', 'B', 'C');
}
hanoi_tower(n=3, from = 'A', tmp = 'B', to = 'C'){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n=3-1=2, from = 'A', tmp = 'C', to = 'B'){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n=2-1=1, from = 'A', tmp = 'B', to = 'C'){
if( n ==1 ) cout << "원판 1을 " <<from='A'<<"에서 " << to='C'<< "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
cout << "원판 " << n << "을 " << from='A'<< "에서 " << to='B'<< "로 이동합니다." <<endl;
hanoi_tower(n=2-1=1, from = 'C', tmp = 'A', to = 'B'){
if( n ==1 ) cout << "원판 1을 " <<from='C'<<"에서 " << to='B'<< "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
}
}
cout << "원판 " << n=3 << "을 " << from='A' << "에서 " << to='C' << "로 이동합니다." <<endl;
hanoi_tower(n=3-1=2, from = 'B', tmp = 'A', to = 'C'){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n=2-1=1, from = 'B', tmp = 'C', to = 'A'){
if( n ==1 ) cout << "원판 1을 " <<from='B' <<"에서 " << to='A' << "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
cout << "원판 " << n << "을 " << from='B' << "에서 " << to='C' << "로 이동합니다." <<endl;
hanoi_tower(n=2-1=1, from = 'A', tmp = 'B', to = 'C'){
if( n ==1 ) cout << "원판 1을 " <<from='A'<<"에서 " << to='C'<< "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
}
}
}
}
실행결과는 다음과 같습니다.
원판1은 A에서 C를 거쳐 B로 이동했고 (from='A'에서 tmp='B'로 이동, [그림1] 결과화면 : 첫번째 줄 세번째 줄)
원판2는 A에서 B로 이동했습니다. (from='A'에서 tmp='B'로 이동, [그림1] 결과화면 : 두번째 줄)
> n-1개의 원판(n보다 작은 n-1개의 원판)이 from에서 tmp로 이동
원판3은 A에서 C로 이동했습니다. (from='A'에서 to='C'로 이동, [그림1] 결과화면 : 네번째 줄)
> 원판n이 from에서 to로 이동
원판1은 B에서 A를 거쳐 C로 이동했고 (tmp='B'에서 to='C'로 이동, [그림1] 결과화면 : 다섯번째 줄 일곱번째 줄)
원판2는 B에서 C로 이동했습니다. (tmp='B'에서 to='C'로 이동, [그림1] 결과화면 : 여섯번째 줄)
> n-1개의 원판(n보다 작은 n-1개의 원판)이 tmp에서 to로 이동
대략,
원판 n과 n-1개(n을 제외한 원판 중, n보다 작은 n-1개의 원판)의 원판 사이에
어떤 관계가 있다는 것을 확인하셨을 것입니다.
즉,
n보다 작은 n-1개의 원판은 from->tmp로 이동하고
원판n은 from->to로 이동하고
n보다 작은 n-1개의 원판이 tmp->to로 이동하는 것을 확인하실 수 있습니다.
그러면 이제 n개의 관점에서 하노이타워를 공부해보기로 합니다.
하노이타워를 한글로 풀어서 설명하자면 다음과 같은 실행 순서를 따릅니다.
1) 가장 큰 원판을 제외한 나머지 원판(n-1개)를 tmp에 옮기고,
2) 가장 큰 맨 아래의 원판을 to로 옮기고,
3) 가장 큰 원판을 제외한 나머지 원판(n-1개)를 to로 옮겨야 합니다.
이것을 그림으로 다시 확인해보도록 하겠습니다. (파란색은 하나의 '덩어리'로 보아야 하기 때문에 구분선조차 집어넣지 않았습니다. 보기에 불편하시더라도 하나의 '덩어리'로 봐주세요)
다음 그림은 가장 처음의 배치입니다. 파란색과 빨간색 원판은 모두 from 위치에서 시작합니다.
이제 이동을 시작합니다.
1) 가장 큰 원판(빨간색)을 제외한 나머지 원판(n-1개. 파란색 부분)을(from에서) tmp로 옮기고,
2) 가장 큰 맨 아래의 원판(빨간색)을(from에서) to로 옮기고,
3) 가장 큰 원판(빨간색)을 제외한 나머지 원판(n-1개. 파란색 부분)을(tmp에서) to로 옮깁니다.
이 설명을 코드로 표현한다면 다음과 같습니다.
1) hanoi_tower(n-1, from , to , tmp ); //n-1개를 몽땅 from 에서 tmp로 보냅니다.
2) cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
//가장 큰 마지막 원판 1개를 from에서 to 로 보냅니다.
3) hanoi_tower(n-1, tmp , from , to ); //n-1개를 몽땅 tmp에서 to로 보냅니다.
색깔별로 표시된 부분을 잘 살펴 보세요.
그리고 이 말을 다시 붙여서 간결하게 확인해보면 (위의 원판의 그림 색깔과 함께 참고해 주세요)
hanoi_tower();
출력문
hanoi_tower();
이렇게 샌드위치 구조로 이루어져 있습니다.
위의 그림과 같이 보셨을때 조금은 느낌이 오셨을까요?
이제 직관적으로 이해해보려는 시도를 했으니, 코드에서 어떻게 동작하는지 알아보기로 합니다.
하노이 타워를 학습할 때 가장 중요하게 생각해야 하는 부분은 다음과 같습니다.
[무엇이 이동 하는가?]
하노이 타워의 함수 원형을 살펴보면 다음과 같습니다.
void hanoi_tower(int n, char from, char tmp, char to);
매개변수중 char형 변수는 from과 tmp, to가 있습니다.
세가지의 매개변수가 존재하기 때문에 아주 복잡하게 느껴지지만
사실상, 이동에 관여하는 매개변수는
from과 to에 불과합니다.
왜 그런지 살펴보도록 합시다.
다음의 출력문(cout)을 확인합니다.
void hanoi_tower(int n, char from, char tmp, char to){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
그리고 출력된 내용을 확인합니다.
숫자에 작게 네모칸 표시되어있는 부분을 기준으로 앞/뒤 출력문이 완전히 대칭을 이루는 것을 확인하실 수 있습니다.
원판이 5개만 되더라도 굉장히 많고 복잡하기 때문에 3개를 이동하는 부분만 살펴보도록 하겠습니다.
만약 이해하셨다면 5개 이동의 시작부터 확인해보시면 좋을것 같아요.
숫자에 작게 네모칸 표시되어있는 부분을 기준으로 앞/뒤 출력문이 완전히 대칭을 이루는 것을 확인하실 수 있습니다.
이해하기 쉬운 그림으로 다시 표현해보겠습니다. 아래의 그림을 확인해주세요.
원판3을 A에서 C로 이동하기 위해서
원판1과 원판2를 이동해야 합니다.
즉, from은 A이고 to는 C인 셈이죠. 따라서 자연스럽게 tmp는 B가 됩니다.
현재 원판의 개수는 3개입니다. (원판1, 원판2, 원판3)
1) 원판1과 원판2를 합쳐서 '덩어리'라고 생각한다면 A(from)에서 B(tmp)로 이동하는 것을 보실 수 있습니다. (물론 원판1은 C를 거쳐 B로 이동하지만 결국에는 B로 이동하기 때문에 통틀어 A에서 B로 이동합니다)
2) 가장 큰 원판 3이 A(from)에서 C(to)로 이동합니다.
3) 원판1과 원판2를 합쳐서 '덩어리'라고 생각한다면 B(tmp)에서 C(to)로 이동하는 것을 보실 수 있습니다. (물론 원판1은 A를 거쳐 C로 이동하지만 결국에는 C로 이동하기 때문에 통틀어 B에서 C로 이동합니다)
더보기를 눌러서 5개의 원판이 어떻게 이동하는지 한번 고민해보시기 바랍니다.
그러면 이제 hanoi_tower의 매개변수가 어떻게 작용하는지 이해가 되실까요?
다시한번 코드를 살펴보도록 하겠습니다.
void hanoi_tower(int n, char from, char tmp, char to){
if( n ==1 ) cout << "원판 1을 " <<from <<"에서 " << to << "로 이동합니다." <<endl;
else{
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from<< "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
}
}
복습을 하면서 가장 크게 헤맸던 부분은 from, tmp, to 어떤것이 이동하는지 여부였습니다.
가장 명심해야할 부분은
모든 원판은 cout(출력문)을 통해 이동한다는 것입니다.
사실 hanoi_tower() 함수에는 출력문이 딱 한가지 구조로 되어있습니다.
from과 to 두 개의 변수로만 사용됩니다.
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
그렇다면 hanoi_tower() 함수의 원형을 다시 살펴보기로 합니다.
void hanoi_tower(int n, char from, char tmp, char to);
즉, hanoi_tower()함수의 두번째 자리에서 네번째 자리의 매개변수로 이동한다는 것을 알 수 있습니다.
따라서, 구조를 다시 살펴본다면 다음과 같습니다.
파란색 블럭 '덩어리'와 빨간색 블럭으로 다시 표현해보겠습니다.
hanoi_tower(n-1, from, to, tmp);
cout << "원판 " << n << "을 " << from << "에서 " << to << "로 이동합니다." <<endl;
hanoi_tower(n-1, tmp, from, to);
그리고 다음 그림을 from과 tmp, to의 위치를 보며 다시한번 살펴봅시다.
다음 그림은 가장 처음의 배치입니다. 파란색과 빨간색 원판은 모두 from 위치에서 시작합니다.
이제 이동을 시작합니다.
1) 가장 큰 원판(빨간색)을 제외한 나머지 원판(n-1개. 파란색 부분)을(from에서) tmp로 옮기고,
2) 가장 큰 맨 아래의 원판(빨간색)을(from에서) to로 옮기고,
3) 가장 큰 원판(빨간색)을 제외한 나머지 원판(n-1개. 파란색 부분)을(tmp에서) to로 옮깁니다.
이제 하노이 타워의 구조를 어느정도 이해하셨나요?
리컬젼 구조를 이해하기에는 하노이 타워가 맞는데.. 저는 이해하는데 정말 어려웠던것 같습니다.
'--------------------*** > 자료구조' 카테고리의 다른 글
| Stack/Queue (0) | 2020.03.03 |
|---|---|
| 스택 중위표기식을 후위표기식으로 전환 (0) | 2020.02.20 |
| [주소와 포인터] 복습 (0) | 2020.02.18 |
| [배열] 2차원 배열 복습 (0) | 2020.02.17 |
| [배열] 1차원 배열 복습 (0) | 2020.02.17 |
