하노이 타워 (The Tower of Hanoi)

조건

- 원반은 한 번에 하나만 옮길 수 있다

- 작은 원반 위에 큰 원반을 올릴 수 없다

패턴 분석

C를 3으로 옮기고자 할 때, A와 B를 2에 옮겨 놓으면 가능하다. -> B를 2로 옮기고자 할 때, A를 3에 옮겨 놓으면 가능하다.

이번엔 4개 (위에서부터 아래로 A,B,C,D)

D를 3으로 옮기고자 할 때, A,B,C를 2로 옮겨 놓으면 가능하다. -> C를 2로 옮기고자 할 때, A,B를 3으로 옮겨 놓으면 가능하다. -> B를 3으로 옮기고자 할 때, A를 2로 옮겨 놓으면 가능하다.

... 같은 방식으로 몇 개의 원반이 있던 간에 어떠한 동일 패턴이 존재한다는 것을 알 수 있다.

이를 다시 일반적으로 표현해보면,

n개의 원반이 있다고 할 때 (위에서부터 아래로 1,2...n번째)

1~(n-1)번째 원반을 2로 옮긴다 -> n번째 원반을 3으로 옮긴다 -> 1~(n-1)번째 원반을 3으로 옮긴다

재귀적 구현

#include<iostream> using namespace std; void Hanoi(int n, int from, int by, int to){ //n개의 원반을, 어디에서, 무엇을 거쳐서, 어디로 움직일 것인가 if (n == 1) //재귀 탈출 cout << from << "에서 " <<to << "로 " << n << "번째 원반을 이동" << endl; //마지막 가장 큰 원반(n)을 3으로 이동 Hanoi(n - 1, from, to, by); //1~n-1개의 원반을 1에서 3을 거쳐 2로 이동 cout << from << "에서" <<to << "로 " << n << "번째 원반을 이동" << endl; // n번째 원반을 3으로 이동 Hanoi(n - 1, by, from, to); //1~n-1개의 원반을 2에서 1을 거쳐 3으로 이동 } void main(){ int n; cout << "원반의 개수를 입력하세요: "; cin >> n; Hanoi(n, 1, 2, 3); }