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

문제

입출력

풀이

나는 지뢰찾기 네모로직 이런 류의 게임을 참 좋아하는데
과거 한창 때 하노이 탑에 중독되었던 적이 있다.
어린 두뇌와 게임 중독 버프로 순식간에 풀어버리곤 했는데
세월이 흘러 이딴식으로 마주하게 되어 속상할 따름이다
(헛소리)

게임은 할 줄 아는데 이걸 재귀로 만들어보려 늙은 뇌를 쥐어짜봤지만
내 최선은 가장 아래에 있는 넘을 세 번째 기둥으로 갖다 놓으려면
그 위에 업은 애들은 두 번째 기둥에 남아있어야겠군 정도였다

알고보니 이 아이디어가 하노이 재귀 함수의 전부였다!
엠지답게 멋진 유튜브 강의를 통해 함수 원리 이해완.

보통 콘솔로 옮기는 과정을 표현하는데
그 과정을 출력하고 몇 번의 이동이 있었는지도 알아야하기에
콘솔을 찍는 대신 벡터에 이동하는 경로를 담아주었다.
함수에서 빠져나온 뒤 벡터의 크기와 데이터를 차례로 출력하면 끗

코드

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

vector<pair<int, int>> v;

void hanoi(int n, int from, int mid, int to) {
	if (n == 0) return;
	hanoi(n - 1, from, to, mid);
	v.push_back({ from, to });
	hanoi(n - 1, mid, from, to);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	hanoi(n, 1, 2, 3);
	cout << v.size() << "\n";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i].first << " " << v[i].second << "\n";
	}

	return 0;
}

채점