[C++] towerOfHanoi

 📌 순환알고리즘 하노이 타워 문제

원반의 개수를 3에서 10까지 변경하면서 그 결과를 확인해 본다. 또한 디스크 이동 횟수도 확인해 볼 것.

 

** 화면 출력 예 (위치 지점을 A, B, C라고 한 경우의 예) :

#1. 디스크 1개를 A지점에서 C로 옮긴다.

#2. 디스크 1개를 B지점에서 B로 옮긴다.

.......

(*출력 줄의 수는 디스크 이동 횟수를 의미)

 

 📌 풀이

출처: https://ledgku.tistory.com/39

가장 큰(맨 밑) 원판과 나머지로 나누어서 생각해보면 가장 큰 원판을 뺀 나머지를 B로 옮긴 후 가장 큰 원판을 C로 옮기고 다시 나머지를 B에서 C로 옮긴다.

 

즉, 단계마다 가장 큰 원판을 제외한 나머지는 모두 B를 거쳐서 C를 간다는 것이다. (출발지에서 경유지를 들려서 목적지에 도착함.)

 

그러면 재귀 함수를 사용해서 예를 들어 원판이 5개가 있고 1, 2, 3, 4, 5를 크기순이라고 치면

1. 1~4를 B로 옮기고 5를 C로 옮긴다.

2. 1~3을 A로 옮기고 4를 C로 옮긴다.

3. 1~2를 B로 옮기고 3을 C로 옮긴다.

4. 1을 A로 옮기고 2를 C로 옮긴다.

5. 1을 C로 옮긴다.

이렇게 볼 수 있다.

 

 📌 코드1 (주석 참고)

#include <iostream> 
using namespace std;

int cnt = 0; // 이동 횟수에 이용.

void Hanoi(int n, char from, char temp, char to)
// n : 원반개수, from : 원래 위치, temp : 임시 장소, to :목적지
{
	// cnt = pow(2, n) - 1;
	// 가장 밑에 있는 원반을 제외한 모든 원반은 from -> temp -> to로 옮겨진다.

	if (n == 1) {
		cout << "#" << ++cnt << ".디스크 1개를 " << from << "지점에서 " << to << "로 옮긴다." << endl;
	}
	else {
		Hanoi(n - 1, from, to, temp); // 맨 밑 원반을 제외한 모든 원반을 from에서 temp로 옮긴다.
		cout << "#" << ++cnt << ".디스크 1개를 " << from << "지점에서 " << to << "로 옮긴다." << endl; // 맨 밑 원반을 from에서 to로 옮긴다.
		Hanoi(n - 1, temp, from, to); // 맨 밑 원반을 제외한 모든 원반을 temp에서 to로 옮긴다.
	}
}


void main()
{
	int n; //원반의 수

	cout << "원반의 갯수를 입력하세요 : ";
	cin >> n;

	Hanoi(n, 'A', 'B', 'C');    // n개의 원반을 'A'에서 'C'로 이동

	cout << "전체 원반 이동 수(원반수 : " << n << ") = " << cnt << endl;
 }