백준 11729 - 하노이 탑 이동 순서

문제 번호: 11729

문제 제목: 하노이 탑 이동 순서

문제 주소: https://www.acmicpc.net/problem/11729

문제 내용

n개의 하노이 탑을 이동하는데 필요한 횟수와 이동 과정을 출력한다. 이동은 1에서 3으로 옮기는 것을 기준으로 한다.

테스트 케이스

3	7 1 3 1 2 3 2 1 3 2 1 2 3 1 3

문제 풀이

재귀 함수 내에서 재귀함수를 호출 할 때 매개변수를 어떻게 넘겨줄 것이냐를 고려하여야 한다.
메인 함수는 다음과 같이 구성한다.
1. n을 입력 받는다.
2. 재귀 함수를 호출한다. 이 때 매개변수는 n, 출발지, 목적지, 결과 문자열 이다.
3. 하노이 탑에서 반환된 횟수를 출력한다.
4. 결과 문자열 내용을 출력한다.

하노이 탑에서의 재귀함수 호출은 아래와 같이 이루어진다.
1. n-1이 출발지에서 경유지로 이동한다.
2. n이 출발지에서 목적지로 이동한다.
3. n-1이 경유지에서 목적지로 이동한다.
위 구성대로 재귀함수를 짜서 구현하면 된다.

풀이 코드

#include <iostream>
#include <string>
using namespace std;

void BAEKJOON_11729()
{
	int N;
	cin >> N;
	string moveLog = "";
	cout << hanoiMove(N, '1', '2', '3', moveLog) << "\n";
	cout << moveLog;
	return;
}

int hanoiMove(int count, char from, char by, char to, string& moveLog)
{
	if (count == 1)
	{
		moveLog.push_back(from);
		moveLog.push_back(' ');
		moveLog.push_back(to);
		moveLog.push_back('\n');
		return 1;
	}
	int ret = 0;
	ret += hanoiMove(count - 1, from, to, by, moveLog);
	ret++;
	moveLog.push_back(from);
	moveLog.push_back(' ');
	moveLog.push_back(to);
	moveLog.push_back('\n');
	ret += hanoiMove(count - 1, by, from, to, moveLog);
	return ret;
}