백준/분할 정복
(c++)백준 11729번: 하노이 탑 이동 순서
Nimgnoej
2020. 6. 25. 14:56
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net

[풀이]
하노이의 탑 알고리즘
아래 순서대로 재귀
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;
}