[11729] 하노이 탑 이동 순서(C++)

 

* 접근한 방법
- 하노이탑 이동의 규칙성을 찾음

- 하노이탑 개수에 따른 이동 횟수
   :  1개 => 1회,    2개 => 3회,    3개 => 7회,    · · ·    
      ☞ 2 * (n -1)의 하노이 이동 횟수 + 1

즉, 하노이는 n-1개를 2번에 옮기고 n을 1번에서 3번으로 옮긴 후 다시 n-1개를 2번에서 3번을 옮기는 것과 같음

hanoi(n - 1, from, to, by);
path.push_back(make_pair(from, to));
hanoi(n - 1, by, from, to);

ex) 하노이 탑 4개는 
     1~3의 하노이를 2번자리에 옮긴 후 
     4번 하노이를 3번자리에 옮기고 
     또 다시 1~3의 하노이를 3번자리로 옮긴다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<pair<int, int>> path;

void hanoi(int n, int from, int by, int to)
{
	if (n == 1) 
		path.push_back(make_pair(from, to));
	else
	{
		hanoi(n - 1, from, to, by);
		path.push_back(make_pair(from, to));
		hanoi(n - 1, by, from, to);
	}
}

int main() {
	int n;
	cin >> n;

	hanoi(n, 1, 2, 3);
	cout << path.size() << "\n";
	for (int i = 0; i < path.size(); i++)
	{
		cout << path[i].first << " " << path[i].second << "\n";
	}
}