[Algorithm/C++] 하노이 타워 원반 이동 횟수 구하기

2022.09.13 - 컴퓨터알고리즘 과제

• 재귀함수를 이용한 알고리즘 풀이

 

<3개의 원반이 있을 경우>

1. 기둥(A, B, C)과 원반 3개(아래부터 a, b, c)가 있을 경우, 맨 아래 원반(a)을 제외하고 위의 2개(b, c)의 원반만 존재한다 생각한다. (처음 기둥 A, 목적지 기둥 C)
2. 다시 2개(b, c)의 원반이 있을 경우, 맨 아래 원반(b)을 제외하고 위의 1개(c)의 원반만 존재한다 생각한다.
3. 첫번째 원반(c)을 다른 기둥(C)으로 이동시킨다.
4. 2번째 원반(b)을 다른 기둥(B)으로 이동시킨다.
5. 첫번째 원반(c)을 2번째 원반(b) 위로 이동시킨다. (b, c 모두 B에 있음)
6. 맨 아래 원반(a)를 목적지 기둥(C)로 이동시킨다.
7. 첫번째 원반을 비어있는 기둥(A)으로 이동시킨다. (A: c, B: b, C: a)
8. 2번째 원반(b)을 목적지 기둥(C)으로 이동시킨다. (c 위에 b 있음)
9. 첫번째 원반(c)을 목적지 기둥(C)으로 이동시킨다. (모두 C로 이동)

2개를 옮기는 작업을 3번
3개(1+2개)를 옮기는 작업을 3번 ... 

 

1개 = 1번

 

2개 = 1 * 2 + 1 = 3번

3개 = 2번 옮기는 경우 2번하고 1번(마지막 원반) 옮겨
      = 3 * 2 + 1 = 7번

4개 = 3번 옮기는 경우 1번 하고 1번 옮겨
       = 7 * 2 + 1 = 15번

5개 = 4번 옮기는 경우 2번하고 1번 옮겨
     = 15 * 2 + 1 = 31번

=> 원반 n개 : 2^n - 1 번

 

위와 같은 방식으로 5개, 10개의 경우도 구할 수 있다.

#include <iostream> 
using namespace std;

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

void Hanoi(int n, char from, char temp, char to) 
// n : 원반개수, from : 원래 위치, temp : 임시 장소, to :목적지
{

	// 프로그램을 완성하세요
	// ......
	if (n == 1) {	// 원반이 1개라면
		cnt++;		// 이동 횟수 1증가
		return;
	}
	else {
		cnt++;		// 이동 횟수 1증가
		Hanoi(n - 1, from, to, temp);	// 원반보다 하나 적은 n-1개의 원반을 임시 장소로 이동		
		Hanoi(n - 1, temp, from, to);	// 임시 장소로 이동시킨 원반을 목적지로 이동
	}

}


void main()
{
	int n; //원반의 수
	
	cout << "원반의 갯수를 입력하세요 : ";
	cin >> n;

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

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