백준 11729(하노이탑)
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5
www.acmicpc.net
하노이 탑은 보통 재귀함수 또는 동적 프로그래밍으로 값을 빠르게 구할 수 있다.
단, 11729번 문제에서는 이동 순서를 나타내야한다.
값만 구한다는 고정관념에 너무 사로잡혀 있어서 이동순서를 보았을 때 당황했다.
재귀 + 분할 정복 문제로 쉽게 생각해보면 조그마한 절차가 반복되는 구조임을 알 수 있다.
하노이 탑 기본 재귀구조는 n개의 탑이 있을 때 , n-1개의 탑을 잠시 다른 곳에 두고 1개의 원판을 움직일 곳으로 옮긴 후 나머지 n-1개의 탑을 그 위에 쌓는 구조로 되어 있다.
이를, from에서 by를 거쳐 to로 가는 형식으로 생각해보았을 때
1. 초기 탑이 쌓여져 있는 from에서 (n-1)개를 일단 거쳐가야할 by로 이동을 시킨다.
2. 이후 남은 하나를 비어있는 to로 옮긴다.
3. 거쳐가야할 by에 옮겨놓은 n-1개의 탑을 to 위에 쌓는다.
의 이동 구조를 가진다.
코드는 다음과 같다.
#include <stdio.h>
int hanoi(int);
void hanoi_print(int, int, int, int);
int main()
{
int num;
scanf("%d",&num);
printf("%d\n", hanoi(num));
hanoi_print(1,2,3,num);
}
int hanoi(int num)
{
if(num ==1 )
return 1 ;
return hanoi(num-1)*2 + 1;
}
void hanoi_print(int from, int by, int to, int num)
{
if(num == 1)
{
printf("from : %d to : %d\n",from,to);
return;
}
hanoi_print(from,to,by,num-1);
printf("from: %d to : %d\n",from, to);
hanoi_print(by,from,to,num-1);
}
너무 고정관념에 박혀있지 말고 분할 정복 문제일 경우 조그마한 경우 부터 패턴을 찾아나가도록 한다.