오늘도 C코딩 하나를 소개 합니다. 꽤 유명하고 코딩을 배웠던 분들이라면 한번쯤 해보셨을 거에요. 학교에서 C언어를 배운 분들이면 과제로 잘 내주는 주제이기도 해서 코딩으 다들 해보셨을 거에요. 10년도 넘었던 것 같은데 아직도 검색하면 최근 post로 회자되고 있지요. 오늘은 그냥 추억의 코딩 post로 보셨으면 하네요.
하노이의 탑은 세개의 기둥을 기준으로 다양한 크기의 원판을 한쪽 기둥에 크기 별로 순차적으로 쌓기 놀이입니다.
위 그림과 같이 3개의 원판이 있을 때 이 세개의 원판을 오른쪽 끝 기둥에 순차적으로 쌓는 방법을 알고리즘으로 만들어서 코딩화 할 수 있습니다. 쌓는 조건은 시작 위치에서 빈 아무 기둥에 원판을 올려 놓을 수 있습니다.
단, 조건은 작은 원판은 큰 원판 밑에 둘 수 없다는 조건하에 지정 된 기둥으로 원판을 순차적으로 쌓으면 됩니다.
어린시절에 이런 놀이기구가 있어 실제로 해보신 분들이 아마 있을 거에요. 컴퓨터 상에서는 코딩을 통해 쌓을 수 있는데 그 코딩을 소개 합니다.
책이나 기타 조금만 검색하셔도 쉽게 찾을 수 있는 아주 유명한 알고리즘입니다. 제가 만들 수 있지만 이 알고리즘을 본 것이 10년이 훌쩍 넘었네요. 이 알고리즘 표현이 너무 완벽해서 그냥 유명한 알고리즘을 소개 합니다.
void hanoi_tower(int n,char from,char temp,char to)
{
if(n==1)
printf("원판 1가 %c에서 %c로 이동\n",from,to);
else
{
hanoi_tower(n-1,from,to,temp);
printf("원판 %d가 %c에서 %c로 이동\n",n,from,to);
hanoi_tower(n-1,temp,from,to);
}
}
처음 보시는 분들은 약간 어렵게 보일 수 있습니다. from, temp, to 변수명으로 나열하고 재귀호출문입니다. 그런데 정확히 어떻게 원판이 이동하는지 눈으로는 잘 이해가 안되시는 분들이 많습니다. 참고로, 이 알고리즘을 컴파일해서 실행 시켜보시고 그 결과를 눈으로 확인해보고 나서 이 알고리즘을 이해하는데 도움이 될 꺼에요.
사실 이 알고리즘은 결과만 따지면 printf문을 생략하셔도 됩니다. 하지만 어떤식으로 원판이 이동했는지 보기 위해서는 위와 같이 배치하셔야 원판의 이동 경로를 이해할 수 있습니다.
#include
void hanoi_tower(int n,char from,char temp,char to)
{
if(n==1)
printf("원판 1가 %c에서 %c로 이동\n",from,to);
else
{
hanoi_tower(n-1,from,to,temp);
printf("원판 %d가 %c에서 %c로 이동\n",n,from,to);
hanoi_tower(n-1,temp,from,to);
}
}
void main()
{
int n;
printf("하노이탑 입력 : ");
scanf("%d",&n);
printf("")
hanoi_tower(n,'A','B','C');
}
하노이 탑 입력은 원판의 갯수(n)입니다. 그리고, 처음 기둥은, A, B, C로 선언합니다.
실행은 원판 3개를 입력으로 돌립니다.
3개의 원판이 A에 크기별로 쌓여있고 C로 하노이의 탑 알고리즘으로 이동하면 아래와 같은 결과를 얻게 됩니다.
[결과]
대충 원판의 이동을 결과로 느낄 수 있겠죠.
참고로, 재귀호출 할때 메모장에서 기둥 from, temp, to 변수가 hanoi_tower()함수 인자로 어떻게 바뀌는지 적어보세요. 그래야 이해하실 수 있을 거에요. 계속 hanoi_tower()함수의 들어가는 인자가 처음에는 A, B, C 순서 였지만 그 값이 from, temp, to 변수로 넘겨줌으로서 위치가 계속 다음 재귀호출때에 바뀌게 됩니다.
아니면 알고리즘 로직을 따라 원판을 위 그림처럼 이면지 같은 곳에서 그림으로 그려서 한번 이동 시켜 보세요.
사실 더 큰 수로 n의 값을 지정 하여 살펴 볼 수 있겠지만 그러면 결과 이미지가 너무 길어지고 딱 3개의 원판으로 하고 실행을 시켜보는게 이상적인 것 같아요.
추가로, 실행은 3개 이상의 원판을 돌려보세요.