[백준/BOJ] 백준 11729번 : 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

현재 장대에 위치한 n개를 목표하는 장대에 옮려면, 우선 현재 장대의 위의 n-1개를 임시로 사용할 장대에 옮겨 놓고, 현재 장대의 가장 밑에 있는 원판을 목표하는 장대로 옮기고, 임시로 놓아둔 장대의 n-1개를 다시 목표하는 장대로 옮겨 놓는 과정으로 문제를 해결했다.

 

코드

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

int n;
vector<pair<int, int>> result;

//1에 위치한 n개를 3에 옮려면, 우선 1의 위의 n-1개를 2에 옮기고, 1의 가장 밑에 있는 원판을 3으로 옮겨야 한다

//from:n개가 있는 위치
//to: n개를 옮길 위치
//temp: 중간에 이용할 위치
void solve(int n, int from, int temp, int to) {
	if (n == 1) {
		result.push_back(make_pair(from, to));
		return;
	}

	//from의 위의 n-1개를 우선 temp에 옮긴다
	solve(n - 1, from, to, temp);

	//from의 제일 하단의 원판을 to로 옮긴다
	result.push_back(make_pair(from, to));

	//temp에 옮겨 놓았던 n-1개의 원판을 to로 옮긴다
	solve(n - 1, temp, from, to);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	solve(n, 1, 2, 3);

	cout << result.size() << "\n"; //2^n - 1

	for (int i = 0; i < result.size(); i++) {
		cout << result[i].first << " " << result[i].second << "\n";
	}

	return 0;
}