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

1. 문제

 

 

2. 접근 방법

 

자료구조를 배울 때, '재귀' 하면 바로 떠오르는 것이 이 문제이다.

그 만큼 가장 재귀를 잘 설명하는 문제가 되며, 재귀의 강력함을 잘 보여주는 사례라고도 할 수 있다.

 

접근 방법은 이렇다.

첫 장대를 A, 가운데 장대를 B, 목적지 장대를 C라고 한다면

N개의 원판을 이동시키려면, N - 1 개의 원판을 B에 옮긴 후, 나머지 1개를 C에 옮긴다.

그 후, B에 있는 N - 1 개의 원판을 다시 C로 옮기면 되는 것이다.

 

이러한 접근 방식은 또 다시 N - 2개의 원판을 옮기는 문제로 분할되어

분할 정복 방식으로 문제가 풀어지는 것이다.

 

 

3. 코드

#include <iostream>
#include <cmath>

void hanoi(int from, int to, int by, int num)
{
	if (num == 0)
	{
		return;
	}

	hanoi(from, by, to, num - 1);
	printf("%d %d\n", from, to);
	hanoi(by, to, from, num - 1);
}

int main(void)
{
	int N;

	scanf("%d", &N);

	int i = pow(2, N) - 1;

	printf("%d\n", i);

	hanoi(1, 3, 2, N);

	return 0;
}