[Baekjoon][#11729] 하노이 탑 이동순서

• [ 장르 ] 재귀함수
• [ 문제 ]

11729번: 하노이 탑 이동 순서

• My Code

#include <iostream>
using namespace std;
 
void HanoiCount(int n);
void Hanoiprint(int start, int from, int end, int n);
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int num;
	cin >> num;
	HanoiCount(num);
	Hanoiprint(1, 2, 3, num);
	return 0;
}
void HanoiCount(int n)	// 하노이 탑 과정 수는 N개의 원반 수에 대해 (2^N -1)번
{
	int Pow = 1;
	for (int i = 0; i < n; i++)
		Pow *= 2;
	cout << Pow - 1 << '\n';
}
void Hanoiprint(int start, int from, int end, int n)
{
	if (n == 1)
		cout << start << ' ' << end << '\n';	// 기둥에 원반이 하나 남았을 경우
	else
	{
		Hanoiprint(start,end,from,n - 1);	// 그렇지 않으면 기둥의 마지막을 제외한 n-1개의 원반을 가운데 기둥에 옮기고
		cout << start << ' ' << end << '\n';	// 하나남은거 옮기고
		Hanoiprint(from, start, end, n - 1);	// 가운데 옮겼던 나머지기둥 목적지 기둥에 옮김
	}
}

" 재귀는 가장 작은단위 ( Base Case )만 생각해 놓으면, 나머지 남은 여러 큰 상황들은 남은것끼리 또 재귀로 해결한다는 생각 ! "

• [ CheckPoint ]
  

1. 재귀함수의 대표적인 문제 중 하나인 하노이탑 문제이다. 하노이 탑의 성립 조건은 3개의 기둥 ( A,B,C ) 이라고 치자.
   A기둥의 크기가 다른 N개의 원반이 크기가 큰 순으로 쌓여있다. 목표는 C 기둥에 처음 상태 그대로 원반을 옮기는 것이다.
   
2. 주의사항은, 하노이탑의 원반들은 자기보다 큰 원반을 위에 쌓지 못한다. 그리고 한번에 한개의 원반만 옮길 수 있다.
3. N개의 원반을 하노이탑을 통해 처리하면, 항상 총 실행횟수는 (2^N - 1) 회 실행하게 된다.
4. 재귀함수 성질을 이용하는 것이 포인트인 문제. 재귀는 쉽게 생각할수록 좋다. 뭔가 반복적인 일을 수행할 때, 가장 작은 일의 단위인Base Case만 잘 생각하고, 나머지 많은 작업들은 또 다시 재귀를 통해 해결한다는 생각으로 코드를 작성하면 해결된다.
5. 이 문제 역시 로직을 잘 짜도, C++로 풀 경우 출력실행시간때문에 시간초과가 발생하기 떄문에, 코드 도입부에 C++입출력 개선코드를 삽입하고 개행도 endl보다 '\n'을 사용하면 해결 된다.