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

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

11729번: 하노이 탑 이동 순서

 

 

재귀를 이용하는 문제다.

 

단계별 풀기를 하고 있는데, 아직 이 문제를 풀 순서는 아니지만 재귀 배운 김에 풀어봤다. 

 

 

 

이 문제의 핵심 포인트는 다음과 같다.

 

n개의 원반을 A에서 C로 옮기기 위해서는 n-1개의 원반을 A에서 B로 옮기고, 가장 밑의 원반을 A에서 C로 옮긴 후, 다시 n-1개의 원반을 B에서 C로 옮겨야 한다.

 

따라서 재귀로 귀결되는 것이다.

 

사실 이 문제는 너무 유명한 문제이기도 하고 인터넷에 검색하면 자료가 넘치기 때문에 더 이상 자세히 설명하지는 않겠다.

 

 

 

근데 사실 나도 이미 다른 코드를 본 다음 풀어서 쉽게 푼 거지 아예 이 문제를 접해본 적이 없는 상태로 풀었으면 어려웠을 것 같긴 하다.

 

#include <iostream>

void hanoi(int n, int from, int by, int to)
{
	if (n == 1)
	{
		std::cout << from << ' ' << to << '\n';
	}
	else
	{
		hanoi(n - 1, from, to, by);
		std::cout << from << ' ' << to << '\n';
		hanoi(n - 1, by, from, to);
	}
}

int hanoiCnt(int n)
{
	if (n == 1) return 1;
	return 2 * hanoiCnt(n - 1) + 1;
}

int main()
{
	int n;
	std::cin >> n;
	std::cout << hanoiCnt(n) << '\n';
	hanoi(n, 1, 2, 3);
}

 

 

이 문제는 원반을 옮긴 횟수를 가장 먼저 출력해야 하기 때문에, 이동 횟수를 세는 재귀함수를 따로 만들었다.