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

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

11729번: 하노이 탑 이동 순서

[풀이]

하노이의 탑 알고리즘

아래 순서대로 재귀

1. 맨 아래 원판을 제외하고 나무지 원판 모두를 tmp장대로 옮긴다.

2. 맨 아래 원판을 to장대로 옮긴다.

3. 남은 tmp장대에 있는 판 모두 to장대로 옮긴다.

 

옮긴 횟수를 출력한 뒤 수행 과정을 출력해야 하므로 vector에 수행과정을 정장해두고 재귀가 끝난 뒤 한꺼번에 출력해주었다.

 

 

#include <iostream>
#include <vector>
#include <cstdio>//printf, scanf
using namespace std;

struct Move {
	int from, to;
};

int cnt = 0;
vector<Move>v;//수행 과정 저장

void hanoi(int N, int from, int tmp, int to) {
	if (N == 1) {
		v.push_back({ from,to });
		cnt++;
		return;
	}

	hanoi(N - 1, from, to, tmp);
	v.push_back({ from,to });
	cnt++;
	hanoi(N - 1, tmp, from, to);
}

int main() {
	int N;
	scanf("%d", &N);
	hanoi(N, 1, 2, 3);
	printf("%d\n",cnt);
	for (int i = 0; i < v.size(); i++) {
		printf("%d %d\n", v[i].from, v[i].to);
	}
	return 0;
}