[단계별로 풀어보기][재귀] 하노이탑

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

 

 

solve>

나는 이 문제의 풀이를 생각해냈으나.. 재귀함수를 어떻게 작성하는지 모르겠어서 포기했다.

내가 풀려고 시도했던 풀이부터 설명하겠다.

 

이 문제를 풀기 위해서는 가장 밑에 있는 원판부터 고려한다.

이 문제에서의 재귀함수는 코드의 결과가 인자를 넘기는 단계에서 정해져 있다.

예를 들어 f(5,3)을 호출하면 원판을 5개 지닌 하노이탑은 복잡하게 움직이지만, 결국 세 번째 자리로 움직이게 되어있다.

 

위의 원판부터 움직이도록 함수를 호출하면 끝에 있는 결과도 불확실해질 것이다.

따라서 인자로 넘긴 것들을 확실하게 하기 위해서 5번째 원판부터 고려하는 것이다.

 

나는 어떻게 5번째 원판부터 넘겨 풀까 고민하던 중 하노이탑의 원리에 대해서 생각해보았다.

1) k번째 원판의 위에 있는 원판 덩어리는 현재 있는 곳과 k번째 원판의 목적지가 아닌 곳으로 이동한다.

2) k번째 원판은 목적지로 이동한다.

3) 원판 덩어리는 k번째 원판이 있는 곳으로 이동한다.

이 과정을 재귀적으로 반복하면 문제가 풀릴 것이라 생각했다.

 

그러나 코드 작성은 생각처럼 잘 되지 않았고..

유튜브에서 강의하시는 바킹독님 코드를 찾아냈다.

 

 

 

바킹독님 코드를 보고 상당히 깔끔해서 놀랐다.

6-a-b는 1,2,3 중 a도 b도 아닌 숫자를 뜻한다.

1+2+3-a-b=6-a-b이기 때문이다.

멍청하게도 난 이걸 반복문으로 풀었다

 

하여튼 소스를 해설하자면

위의 소스코드는 내가 위에 말한 원리와 빼박이다.

 

1단계:a에서 6-a-b로 아래 원판을 이동한다.

2단계:b로 원판을 이동한다.

3단계:6-a-b에서 b로 아래 원판을 이동한다.

 

이 과정을 재귀적으로 반복한다.