[백준] 11729번 C++ "하노이 탑 이동 순서" 풀이 / 재귀호출

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

11729번: 하노이 탑 이동 순서

 

 

💡 하노이 탑 이동 순서

 

 

✅ 문제 풀이

• 하노이 탑 문제는 재귀호출을 통해 풀이 할 수 있다.
• 하노이 탑의 다음과 같은 공식 때문이다.
• 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다. 탑 3에 있는 가장 작은 원판을 탑 2로 옮긴다. 탑 2에 있는 가장 작은 원판을 탑 1로 옮긴다. 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다.
• k-1개의 원판은 위 공식을 따르게 된다. 
• 따라서 각 원판을 재귀 호출을 통해 이동 순서를 표현할 수 있다.
• 정리하자면, 1->3->2, 2->1->3 순서로 이동하게 된다.
• 이를 위해 hanoi라는 함수를 선언해준다.
• 이 함수는 현재 원판의 번호(=크기)와 시작(from), 중간(by), 끝(to) 지점을 인자로 갖는다.
  만약 원판의 번호가 1이면 "from to"을 출력하도록 한다.
  그렇지 않다면 hanoi를 호출하고 인자로 원판의 번호-1, from, to, by 순서로 넣어준다. 이는 1->3->2 순서를 나타낸 것이다.
  그리고 이 함수를 호출한 후에는 "from to"를 호출하여 이동 상황을 출력한다.
  그다음, hanoi를 한번 더 호출하여 인자로 원판의 번호-1, by, from, to 순서로 넣어준다. 이는 2->1->3 순서를 나타낸 것이다.
• 따라서 원판 하나에 대해 hanoi 함수는 두번 재귀호출 하므로, 연산이 2^k번 발생하는데, 가장 큰 원판은 바로 이동할 수 있으므로 1을 빼준다. 따라서 총 이동 횟수는 2^k-1이 된다.
• 참고로 c++의 경우, pow함수를 사용할 때 int로 형변환을 해주지 않으면 결과가 틀렸습니다가 나오므로, int로 꼭 변환한 후 -1을 빼주도록 한다. (pow함수의 반환 형태는 double 형이기 때문) 

 

✏ 코드 전문

#include<iostream>
#include<math.h>

using namespace std;

void hanoi(int n, int from, int by, int to) {
	if (n == 1) {
		cout << from << " " << to << "\n";
	}
	else {
		hanoi(n - 1, from, to, by);
		cout << from << " " << to << "\n";
		hanoi(n - 1, by, from, to);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int k;
	cin >> k;

	cout << int(pow(2, k)) - 1 << "\n";
	hanoi(k, 1, 2, 3);

	return 0;
}