실력키우기 하노이의 탑(C++)

1161 : 하노이의 탑

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 874 회    시도횟수: 1329 회   

하노이의 탑에 대한 전설은 아래와 같다.
인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 기둥이 동판 위에 세워져 있다. 기둥 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓여 있다. 이것은 신성한 브라흐마의 탑이다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 기둥으로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮긴다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 된다.

 

기둥을 1, 2, 3 번으로 하고, N개의 원판이 작은 것부터 1, 2, 3, 4 … N이라고 할 때, 아래의 규칙에 따라 모든 원판을 3번 기둥으로 쌓기 위해 이동한다.
1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

 

모든 원판이 1번 기둥에 순서대로 쌓여 있을 때, 3번 기둥으로 모두 이동하는 과정을 순서대로 출력하는 프로그램을 작성하시오.

 

 

1번 기둥에 쌓여 있는 원판의 개수 N(1≤N≤15)이 들어온다.

한 줄에 한 개의 원판을 이동하는 과정을 “원판번호 : 이동전 기둥번호 -> 이동후 기둥번호” 형식으로 모두 출력한다.

[Copy] 3

[Copy] 1 : 1 -> 3 2 : 1 -> 2 1 : 3 -> 2 3 : 1 -> 3 1 : 2 -> 1 2 : 2 -> 3 1 : 1 -> 3

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

/**************************************************************     Problem: 1161     User: a132034     Language: C++     Result: Success     Time:8 ms     Memory:1092 kb ****************************************************************/     #include    <cstdio> #pragma warning(disable:4996)   void hanoi(int n, int from, int tmp, int to) {     if (n == 1)         printf("1 : %d -> %d\n", from, to);     else     {         hanoi(n - 1, from, to, tmp);         printf("%d : %d -> %d\n", n, from, to);         hanoi(n - 1, tmp, from, to);     } }   int main() {     int N;     scanf("%d", &N);     hanoi(N, 1, 2, 3);       return 0; }

하노이의 탑 

알고리즘 뿐만 아니라 어린이들이 생각하는 힘을 길러주기 위한 장난감으로도 사용되는 것으로 알고 있다. 

알고리즘에서도 나름 유명한 문제로 알고있다. 

재귀호출로 풀면 어렵지 않으나 생각하는 것이 상당히... 어렵다.. (개인적으로)

함수의 n은 원판의 갯수

from 에서 to 까지 원판 n개를 옮기는 것이다. 

3일 때 

19번 라인이 실행되게 되어 

hanoi (2, 1, 3, 2)가 된다. 

다시 19번 라인이 실행되게 되고 

honoi (1, 1, 2, 3)이 되어 

1 : 1 -> 3이 출력하고 honoi (1, 1, 2, 3) 종료

hanoi (2, 1, 3, 2)에서 2 : 1 -> 2가 출력되고 

hanoi (1, 3, 1,  2)이 되어 1 : 3 -> 2가 출력되고 종료 

hanoi (2, 1, 3, 2) 종료.

이런식으로 재귀호출이 일어나게 된다. 

1. 맨 아래 판을 제외한 나머지를 모두 tmp로 옮긴다. 

2. 맨 아래 판을 목적지로 옮긴다. 

3. 남은 tmp에 있던 판을 모두 목적지로 옮긴다. 

이것을 실제로 그려보며 함수화 하면 위와 같다.