백준 11729번 하노이 탑 이동 순서 (C++)

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

11729번: 하노이 탑 이동 순서

 

하노이탑은 재귀문제에서 가장 기본적인 문제로 대학 강의에서 처음 배우게 된다. 그러나 나름 어려운 편이고 기본기를 정확히 하자는 의미로 하노이탑을 풀어봤다. 

 

접근법

하노이 탑의 가장 기본적인 요소는 높이가 4인 하노이탑을 3번 막대로 옮기기 위해서는 맨아래 판을 제외하고 높이 3인 탑을 2번 막대로 옮기는 순서가 필요하다. 

그러므로 

 

Hanoi(4) -> Hanoi(3)

 

이렇게 포함이된다는 것이다. 그리고 높이 4인 탑을 1번 기둥에서 3번으로 옮긴다고 하면, 높이 3인 탑을 2번으로 옮겨야한다. 그러므로

 

Hanoi(4, 1번->3번 ) -> Hanoi(3, 1번 -> 2번)

 

이라할 수 있다. 그리고 재귀적인 문제를 위해 어디로 경유 할 것인가? 이것이 문제이다. 그러므로 하나의 파라미터가 더 필요하다.

 

Hanoi(4, 1번에서 2번 경유하고 3번으로) -> Hanoi(3, 1번에서 3번 경유하고 2번으로)

 

이런식으로 재귀가 이루어진다. 이것을 한 번 트리로 나타내어보자.

 

파란색 순서대로 계산이 이루어진다.

 

이것을 코드로 바꿔보면

 

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); // 경유지 들렸으니까 이제 목적지로
	}
}

 

주석을 보면 이해가 쉬울 것이다.

먼저 높이 4를 1번에서 3번으로 옮기고 싶으면 

높이 3을 1번에서 2번으로 옮겨야한다.

그리고 1번에서 2번으로 옮긴다는 것은 재귀적으로 끝까지 내려가서 n이 1일 때 까지 들어가게 된다. 1까지 들어갔다면 모두 경유지에 들어갔다는 의미 이므로 from -> to 출력한다. 목적지까지 갔다는 의미다.

 

그리고 모든 하노이탑의 이동은 위의 저 트리를 모두 순회해야한다. 즉, 하노이탑의 이동 횟수는 이진트리의 노드 갯수와 같다. 

 

하노이탑 개수 : 2^N - 1

 

#include <iostream>
#include <cmath>

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() {
	int N;
	cin >> N;
	cout << (1 << N) - 1 << '\n';
	hanoi(N, 1, 2, 3);
}