하노이탑 문제는 알고리즘계에 있어 고전에 속한다. 특히 재귀호출(Recursion)에 대해 공부할 때 빠지지않고 등장하는 단골 문제이다.
그러나, 실제로 하노이탑 문제 풀이를 깊숙히 이해하는 것은 그리 쉽지 않고, 응용된 문제들은 꽤 어렵다.
이 페이지에서는 기본문제부터 응용문제까지 하나씩 다루도록 하겠다.
1. 기본 - 하노이 탑 이동 순서(백준 11729)
2. 응용 - 중간에 멈춰버린 하노이탑 (백준 2270)
3. 응용 - 하노이이 네 탑 (백준 9942)
---------------
1. 기본 - 하노이 탑 이동 순서(백준 11729) https://www.acmicpc.net/problem/11729
원판 수량이 주어졌을 때, 총 소요되는 이동회수 및 이동순서를 출력하는 문제
풀이
- 장대 A,B,C가 있을 때, A에 있는 원판들을 C로 옮기는 경우를 생각했을 때,
1)원판이 A에 1개만 있는 경우는, A에 있는 것 1개를 직접 C로 옮기면 된다. : (A, C)
2)원판이 A에 2개 있는 경우는, C와 B와 1개씩 옮긴 후, B에 있는 것을 C로 옮기면 된다. : (A,C) (A,B) (B,C)
-원판이 A에 3개 있는 경우는, 위 1번과 2번을 가지고 생각해보자.
. 먼저,A의 위쪽 2개를 2)의 방법 이용해서 B로 옮기고,
. A의 제일 밑에 남은 것을 C로 옮기고 (1번과 같은 방법으로)
. 이제 B에 있는 2개를 C로 2)의 방법을 이용해서 옮기면 된다.
- 위에서와 같이 옮기는 방법을 수식으로 정의해보면,
f(n, A, B, C) : "n개 원판에 대해서 A에 있는 것들을 B를 보조로해서 C로 옮기는 방법" 이라하면,
방법1 = f(1,A,B,C)
방법2 = f(2,A,B,C)
- 원판3개 있는 경우를 수식으로 표현해보면,
f(3,A,B,C) = f(2,A,C,B) + f(1,A,B,C) + f(2,B,A,C)
- 이제 이것을 n개의 원판에 대해 일반화 해보면,
f(n,A,B,C) = f(n-1,A,C,B) + f(1,A,B,C) + f(n-1,B,A,C)
- n개의 원판에 대해서 수행되는 회수는 f(n) = 2*f(n-1)+1 = 2n -1
따라서, 밑에 있는 소스처럼 count함수를 사용하지 않고, 2의 거듭제곱을 바로 계산해서 출력해도 무방
소스
#include <stdio.h>int N;int count(int n){int i,d=1;for(i=2;i<=n;++i) d = 2*d+1;return d;}void hanoi(int n, int a, int b, int c){if(1==n) { printf("%d %d\n",a,c); return; }hanoi(n-1,a,c,b);printf("%d %d\n",a,c);hanoi(n-1,b,a,c);}int main(){scanf("%d",&N);printf("%d\n",count(N));hanoi(N,1,2,3);}
2. 응용 - 중간에 멈춰버린 하노이탑 (백준 2270) https://www.acmicpc.net/problem/2270
원반들을 옮기는 중간에 멈춰선 상태. 최종목표되는 막대기는 어디이며, 다 옮길려면 몇 번 더 이동해야되는가?
풀이
- 이 문제를 풀기 위해서는 하노이탑 문제에서, 원반이 이동될 때의 몇 가지 특징을 이용해야 함.
(특징 1)
i번째 원반을 움직이려고 할 때, 이 i보다 큰 원반들을 움직이는 경우는 발생하지 않는다.
특히 i보다 큰 원반들 (=N, N-1, ... i+1)이 목표막대기에 이미 있는 경우는,
이 큰 원반들을 다시 움직이는 경우는 없다.
(특징2)
i번째 원반을 목표막대기로 옮기기위해서는, 이미 이 목표막대기에는 i보다 큰 원반들이 존재해야 한다.
따라서, 큰 원반부터 시작해서 작은원반 순으로 목표막대기로 이동되어야 한다.
(특징3)
만약 i보다 큰 원반들인 N, N-1,...,i+1 들이 목표막대기에 있다면,
i보다 작은 원반들(=i-1,i-2,...,1)은 i와 같은 막대기에 있으면 안되고,
또한 목표 막대기에 있어서도 안된다.(왜냐면 i를 목표막대기에 옮기려는 것이기에, 더 작은게 있으면 이동불가)
- 문제에서는 n개의 디스크는 목표 막대기에 옮긴 상태이기에 (n>=1), 전체 N개 중에서 최소한 1개는 이동한 상태이고, 위의 특징을 생각해보면 N번 원반은 옮겨진 상태로 봐야 한다. 따라서, 최종 목표 막대기는 N번 원반이 있는 곳임.
- 이제 문제는 N-1번 원반부터 옮기는 것인데, 위 특징에 의해서 이미 목표막대기에 있을 때는 옮길 필요가 없다.
즉, i번째 원반을 옮기려는데, 이 원반이 목표막대기에 이미 있다면, (i-1번~1번)까지만 목표 막대기로 옮기면 됨
if(dst==src) move(i-1,dst);
- 옮기려는 i번째 원반이 dst에 있지 않다면,
1) i-1번~i번 원반을 보조막대기(aux)로 옮기고
2) 그 다음에 i번 원반을 목표막대기(dst)로 옮기고,
3)다시 aux에 있는 (i-1번~1번) 원반들을 dst에 옮기게 될 것이다.
여기서 이동회수 관점에서만 보면,
우리가 하노이탑 문제에서 N개의 원반을 dst에 옮길 때 2N-1만큼 회수가 소요된다는 것을 알고 있기에,
위의 2)번은 (2i-1-1)회 3)번은 1회 이동회수가 걸림을 알 수 있다. 2)번과 3번을 합치면 2i-1번
소스
#include <stdio.h>#define MAXN 100001#define MOD 1000000int N,cnt;int pow2[MAXN],p[MAXN];void move(int disc, int dst){int src = p[disc];int aux = 1 + 2 + 3 - src - dst; //1번,2번,3번 막대기 중에서 src와 dst가 아닌것if(disc<1) return;if(dst!=src){move(disc-1,aux);cnt = (cnt + pow2[disc-1]) % MOD;}else move(disc-1,dst);}int main(){int i;//pow2 미리 계산pow2[0]=1;for(i=1;i<MAXN;++i) pow2[i] = (pow2[i-1]<<1)%MOD;scanf("%d",&N);int a,b,c,x;scanf("%d %d %d",&a,&b,&c);for(i=1;i<=a;++i) { scanf("%d",&x); p[x]=1; }for(i=1;i<=b;++i) { scanf("%d",&x); p[x]=2; }for(i=1;i<=c;++i) { scanf("%d",&x); p[x]=3; }printf("%d\n",p[N]);cnt=0;move(N-1,p[N]);printf("%d\n",cnt);return 0;}- 2의 거듭제곱은 미리구해놔서 속도 세이브 함
- 막대기의 번호를 소스에서와 같이 1,2,3으로 하지 않고, 0,1,2로 하면 0번 막대기에 대한 p[x]값 설정을 안해도되나, 속도에는 마이너.
- move함수를 따로 구현하지 않고 main내에 for루프로 구현한다면 약간의 속도 세이브 생각할 수 있겠음.
3. 응용 - 하노이의 네 탑 (백준 9942) https://www.acmicpc.net/problem/9942
막대기가 4개일 때의 문제.
풀이
- 4개일 때는, 최적의 해라고 증명된 바는 없으나, 일반적으로 다음과 같이 푸는 해가 알려져 있다.
1) n개 원반이 있을 때 k개를 한 막대기에 옮기고,
2) 나머지 (n-k)개를 목표되는 막대에 옮기고,
3) 1번에서 옮겨놨던 k개를 목표 막대기에 옮긴다.
- 문제는 이 k를 어떻게 결정하는가의 문제. 특출한 방법은 없고 1<=k<n 까지에 대해서 대입해서 최솟값을 찾는다.
- 위에서 말한 것을 수식으로 표현하면,
T(n,r) = 2 * T(k,r) + T(n-k, r-1)
막대기가 4개인 경우만을 고려하고, 최솟값이 되게하는 k를 표현하면,
T(n,4) = min(2 * T(k,4) + T(n-k,3)), 1<=k<n
- T(n-k,3)은, 막대기가 3개일 때의 이동횟수로, 2n-k-1가 됨을 알 수있다.
근데, 여기서 n<=1000이기에 long long을 사용하더라도 n>=64의 경우에는 계산이 안된다. (263을 계산할 수 없음. n=64, k=1의 경우)
여기서 문제에서 주어진 조건을 활용하는데, 문제를 보면 답이 long long으로 표현가능하다고 했다.
따라서, 최솟값을 찾는데 있어 (n-k)>=63의 경우는 무시해도 된다.
- 소스에 보면 속도 향상을 위해서, 미리 2의 거듭제곱값을 구해 놨음을 볼 수 있고, 계산된 T(k,4)값을 배열로 저장해서 사용했다.
소스
#include <stdio.h>#include <limits.h>#define MAXN 1001int N;long long pow2[MAXN], T[MAXN];long long move(int n, int r){if(n==1) return 1;long long m = -1;for(int k=1;k<n;++k){if(n-k >= 63) continue;long long kVal = (T[k]==0) ? T[k]=move(k,r) : T[k];long long nkVal = pow2[n-k]-1;long long x = 2 * kVal + nkVal;if(m==-1 || x<m) m=x;}return m;}int main(){pow2[0]=1;for(int i=1;i<MAXN;++i) pow2[i] = pow2[i-1]<<1;int test=0;while(~scanf("%d",&N)){printf("Case %d: %lld\n",++test,move(N,4));}return 0;}-끝-
'알고리즘 > 알고리즘 노트' 카테고리의 다른 글
| [코드모음]-기타 (0) | 2016.08.19 |
|---|---|
| [코드모음] - 문자열 (0) | 2016.08.19 |
| [코드모음]-정렬, 자료구조 (0) | 2016.08.19 |
| [코드모음]-DP (0) | 2016.08.19 |
| [코드모음]-기하, (0) | 2016.08.19 |