이번 문제는 하노이탑 이동 순서에 대해서 출력하는 문제입니다.
입력값으로 첫번째 탑에 쌓여있는 원판들의 개수를 입력 하면 다음과 같은 출력값을 얻을 수 있습니다.
저는 재귀함수를 사용해서 하노이탑 문제를 풀어보았습니다.
hanoi(int i, int from, int to, int sub)를 사용하여 i는 입력받은 값이고 from 장대로 부터 to 장대로 sub 장대를 이용해서 이동하도록 하는 재귀함수입니다. 하노이탑 알고리즘을 사용하면 다음과 같이 코드를 작성 할 수 있습니다.
#include <iostream>
using namespace std;
void hanoi(int i, int from, int to, int sub) { // 1 3 2
if (i == 1)
cout << from << " " << to << "\n";
else {
hanoi(i - 1, from, sub, to); // 1 2 3
cout << from << " " << to << "\n"; // 1 3
hanoi(i - 1, sub, to, from); // 2 3 1
}
}
int main(void) {
int num;
cin >> num;
cout << (1 << num) - 1 << "\n";
hanoi(num, 1, 3, 2);
return 0;
}
