안녕하세요 c++ 공부하고있는 대학생입니다.
이번에는 자료구조 다시 공부하다가, 오랜만에 하노이의탑 문제가 나와서 한번 정리 해 보려고 합니다.
우선 하노이의탑의 조건이
한 번에 하나의 원판만 옮길 수 있다.
큰 원판이 작은 원판 위에 있어서는 안 된다.
이렇게 되어있습니다.
저번에 포스팅했던 것 처럼 제일 중요한건 탈출조건문이므로, 저는 n개의 원판이 있다면 이 원판의 n이 1이되는 순간을 중점으로하여 탈출문을 작성하였습니다.
하노이의탑 처음 보았을때는 원판의 개수가 많아질수록 복잡해보여서 어려워서 직접 3개일때, 4개일때, 5개일때 가정을 해서 혼자 풀어보았습니다.
그랬더니, 패턴이 있다는것을 이해했습니다. 어짜피 모든원판은 3번째 기둥에 가야하므로, 제일 큰 원판을 제외한 모든 원판이 2번쨰 기둥으로 먼저 이동을 한 다음, 제일 큰 원판을 3번째기둥으로 옮기고, 그다음에 2번쨰 기둥에 있는 원판을 다시 3번쨰로 모두 옮기면 끝인걸 확인하였으며, 토탈 최소 움직임에 대한 점화식을 구했습니다.
우선, 3개의 원판이 있다고 가정한다면,
2번쨰로 가는 경우는
1->3
1->2
3->2
이렇게 3번의 움직임을 가집니다.
그리고 마지막 모든 원판이 3번쨰 기둥으로 갈때에는,
1->3
2->1
2->3
1->3
이렇게 4번의 움직임을 가집니다.
그러므로 원판의 개수가 3개일때에는 총 7번의 움직임을 가집니다.
원판의 개수가 4개일때에도 마찬가지입니다.
2번쨰 기둥으로 가는 횟수 7번, 3번째 기둥으로 가는 횟수 8번으로 총 15번의 움직임을 가집니다.
원판의 개수가 5개일때에도 마찬가지입니다.
2번쨰 기둥으로 가는 횟수 15번, 3번째 기둥으로 가는 횟수 16번으로 총 31번의 움직임을 가집니다.
이쯤되면
n=3 -> 7
n=4 -> 15
n=5 -> 31
즉 A(n) = 2^n-1 이 토탈움직임의 횟수임을 확인 할 수 있습니다.
또한, 2번쨰 기둥으로 가는 횟수는 A'(n) = 2^(n-1) -1 임을 확인 할 수 있습니다.
ex ) 원판의 수 n이 3일때, A'(3) = 2^(3-1) -1 = 3
3번째 기둥으로 가는횟수 역시 A''(n) = 2^(n-1) 임을 확인 할 수 있습니다.
ex ) 원판의 수 n이 3일때, A''(3) = 2^(3-1) = 4
그러면 이제 소스코드로 작성 해 보겠습니다.
위에서 말씀드린 것 처럼, 하노이의탑 패턴은 크게 3단계로 나누어져있습니다.
- 가장 큰 원판을 제외한 모든 원판(n-1개) 를 2번째 기둥으로 옮겨버린다.
- 1번째 기둥에 있는 가장 큰 원판을 3번째 기둥으로 옮겨버린다.
- 2번째 기둥에있는 모든 원판을 3번째 기둥으로 옮긴다.
이렇게 정리하면 정말 쉽습니다.
그래서 이 해법 그대로 코딩을 하면 됩니다.
#include <stdio.h>
int count = 0;
int movehanoi(int a, int b){
printf("%d to %d\n",a,b);
count++;
}
int hanoi(int n,int one, int two, int three) {
if(n==1){
movehanoi(one,three);
}
else {
hanoi(n-1,one,three,two);
movehanoi(one,three);
hanoi(n-1,two,one,three);
}
}
int main() {
hanoi(5,1,2,3);
printf("count : %d\n",count);
}코드를 보시면, movehanoi 함수는 원판의 움직임을 보여주는 형태를 보여줍니다.
카운트 라고 변수를 선언한것은 , 토탈 움직임 횟수를 확인 해 보기위해서 입니다.
hanoi 함수에서 int n은 원판의 개수, int one은 첫번째기둥, int two는 두번째기둥, int three는 3번째 기둥을 뜻합니다.
그리고 if(n==1)에서 아까말씀드린 탈출문을 작성하였습니다. 왜 1번째기둥에서 3번째기둥으로 옮긴것이냐 하면, 가장 큰 원판을 마지막 3번쨰기둥으로 옮기기 위함입니다. 하노이의탑 최종 목표가 모든 원판을 3번쨰로 옮기는 것 이므로 그렇게 작성하였습니다.
그리고 else문에서 재귀문으로 hanoi(n-1,one,three,two) 로 하였습니다. 이유는 간단합니다. 가장 큰 원판을 제외한 n-1개를 2번째 기둥으로 옮기기 위함입니다. 그래서 hanoi 재귀문에서 기존에 two three가 바뀌었기때문에, movehanoi에 실질적으로 들어가는 값은 movehanoi(one,two)가 됩니다.
이렇게 재귀문을 빠져나오면, movehanoi(one,three) 에 의해서 1번째기둥에 있는 가장 큰 원판을 3번째기둥으로 옮깁니다.
그리고 마찬가지로 2번째 기둥에서 모든 원판을 3번째기둥으로 옮겨야하기 떄문에,
hanoi(n-1,two,one,three)로 바꾸어주었습니다.
그러면 마찬가지로 movehanoi에 실질적으로 들어가는 값은, movehanoi(two,three)가 되게됩니다.
저 else문을 잘 보시면 아까 위에 정리 해 놓았던 하노이의탑 해법 그대로를 적어놓은걸 확인 할 수 있습니다.
처음에 이 문제를 접근할때에는 생각을 많이 하게 되었지만, 역시 자료구조는 그림을 그리면서, 수식을 생각 해 보면서 하는것이 정답인 것 같습니다.
다음은 제가 메모장으로 적어가면서 풀었던 과정입니다.
한 번에 하나의 원판만 옮길 수 있다.
큰 원판이 작은 원판 위에 있어서는 안 된다.
3개일때 가정해서 풀었더니, 7번의 움직임이 가장 최소
4개 가정시 15번의 움직임
5개 가정시 31번의 움직임
즉, 토탈 무브 횟수는 2^n -1
그리고, 2번쨰기둥으로 가는 횟수는 무조건 2^(n-1) -1
3번쨰기둥 2^(n-1)
해법
1. 무조건 2번쨰로 n개의 원반이 있다면, n-1개를 2번쨰로 놓아야함.
2. 1번째 기둥 원반을 그냥 3으로 이동
3. 2번쨰 기둥에서 모든 원반(n-1개) 무조건 3으로 다 이동시켜야함.
증명
3개원반, 7번움직임
A(2) - A(1) = 8 = 2^3
4개원반, 15번 움직임
A(3) - A(2) = 16 = 2^4
5개원반, 31번 움직임
A(4) - A(3) = 32 = 2^5
6개원반, 63번 움직임
A(1) = 7
A(2) = 15
A(3) = 31
A(4) = 63
잘 보면,
A(2) - A(1) = 8 , A(3) - A(2) = 16 , A(4) - A(3) = 32
계차수열 처럼 보이지만, 등비수열 꼴로 나타나기때문에 계비수열이라 하고,
계비수열 b(n)이라 가정하면,
b(1) = 8
b(2) = 16
b(3) = 32
이 계비수열의 일반항은, b(n) = 8 x 2^(n-1) => 등비수열 일반항 공식 a(n) = a1 x r^(n-1)
즉, 식을 정리하면,
A(n) = A(n-1) + b(n-1) 이므로,
n이 2일때 가정하면,
A(2) = A(1) + b(1)
= 7 + 2^3 *1 = 15
n이 3일때 가정하면,
A(3) = A(2) + b(2) 이므로,
= 15 + 16 = 31
이렇게 성립하게된다.
결론
점화식으로 하자면, 2^n -1 이지만, 수식으로 증명하자면 a(n) = a(n-1) + (8 x 2^(n-1)) (단, n>=2) 임을 알 수 있다.
