하노이의 탑을 해결하는 방법을 출력하는 문제입니다. 사실 하노이의 탑 문제가 유명해서 배정된 난이도에 비해 쉽게 풀게 됩니다.
먼저 이동횟수는 간단한 점화식으로 풀 수 있습니다. 탑에 오직 하나의 원판이 있다면 1회의 이동으로 해결할 수 있습니다. 원판이 2개라면 첫 번째 원판을 가운데에 두고 두 번째 원판을 도착지에 놓은 후 첫 번째 원판을 도착지로 가지고 옵니다. 마찬가지로 개수를 늘려나가면서 해법을 생각해보면 n개의 원판이 있는 하노이의 탑을 해결하는 것은 맨 아래의 원판을 제외한 n-1개의 원판을 가운데에 옮겨 놓고 n번째 원판을 도착지에 옮겨놓은 뒤에 n-1개의 원판을 가운데에서 도착지로 옮기는 것입니다. 즉, n개의 원판이 있는 하노이의 탑은 n-1개의 원판이 있는 하노이의 탑을 2번 실행한 것에 가장 큰 원판을 1회 이동하는 것이 되므로 점화식을 아래와 같이 세울 수 있습니다.
\[a_1=1,a_n=2a_{n-1}+1\\ \text{Assume }a_n=2^n-1\\ n=1\Rightarrow a_1=1=2^1-1\\ n=k\Rightarrow a_k=2^k-1\\ \text{Then }a_{k+1}=2a_k+1=2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1\\ \therefore a_n=2^n-1\]식을 풀었더니 2n-1회의 이동으로 n개의 원판이 있는 하노이의 탑을 풀 수 있다고 합니다. 이제 이동 방법을 출력할 것입니다. 재귀를 이용하여 풀 것인데, 위에서 개수에 대한 점화식을 찾으면서 n개의 원판이 있는 하노이의 탑은 n-1개의 원판을 가운데에 옮기고 n번째 원판을 도착지에 옮기고 n-1개의 원판을 도착지에 옮기는 것이라고 했습니다. 이는 재귀적인 관계에 있습니다. n개의 원판이 있는 하노이의 탑을 푸는 과정은 출발지는 그대로이지만, 도착지가 중간 막대인 n-1개짜리 하노이의 탑의 과정을 진행한 뒤 n번째 원판을 옮기고 출발지가 중간 막대이고 도착지가 그대로인 n-1개짜리 하노이의 탑의 과정을 다시 진행하는 것이라 볼 수 있으므로 이를 구현하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-03-29 00:00:45 |