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

1. 문제 이해

엄청 유명한 하노이 탑 이동순서 문제이다.
백준 재귀 단계별 문제에 마지막 문제였다.

아래 두 가지 컨셉을 이해하는 것이 가장 중요했다.

1. N-1 개의 원판을 가운데로 옮겨야 가장 큰 원판을 맨 오른쪽으로 옮길 수 있다. ! ! !
2. N=1 일 때(원판이 하나일 때)는 그냥 바로 냅다 그 위치로 옮기면 된다.

이 두 가지 컨셉이 그냥 머리속으로 계속 고민할 때는 잘 상상이 안되는데,, 어느 순간 어!? 그게 끝이네? 하는 생각이들면,, 재귀에 저 두 생각이 정말 중요하단 생각이 들었다.

2. 소스 코드

#include<vector>
#include<iostream>
#include<stdio.h>
using namespace std;
int cnt;
vector<vector<int>> ans;
void hano(int n,int f,int b,int t) {
	if (n == 1) {
		cnt++;
		vector<int>sample; sample.push_back(f); sample.push_back(t);
		ans.push_back(sample);
	}
	else {
		hano(n - 1, f, t, b);
		vector<int>sample; sample.push_back(f); sample.push_back(t);
		ans.push_back(sample);
		cnt++;
		hano(n-1,b,f,t);
	}
}
int main() {
	int n;
	cin >> n;
	cnt = 0;
	hano(n, 1, 2, 3);
	cout << cnt << endl;
	for (int i = 0; i < ans.size(); i++) {
		printf("%d %d\n", ans[i][0], ans[i][1]);
	}

}

3. 생각한 풀이 방식

사실 처음 오랜만에 이 문제를 다시 이번에 생각 했을때는,,, 여러 조건문을 사용해서 추적하면서 풀려고했었다..
그렇기 때문에 처음에 좀 많이 헛돌았고,, (저렇게 말도안되는 방식에 재귀는 바로 떠올리진 못했다.)
아는 지인에 이건 좀 쩔기 때문에 한 번 직접 봐보고 풀어도 도움이 될 꺼 같다하여, 먼저 구현 방식을 보게되었다.

풀이에서 F는 시작 , B는 지나가는 원판 , T는 도착점 원판이다.
이를 활용하여, 머릿속에 가장 큰 문제를 풀었고, if 를 통해 가장 작은 부분까지 문제가 도달했을 때 (n=1일 때) 그제서야 옮기는 방식으로 결국 풀어 내었다.

4. 얻어가는 Tip.

수많은 글들을 봤다. 재귀하면 하노이고 하노이 하면 재귀라고,,
진짜 하루동안 이 문제만 밥먹으면서도 유튜브보면서도 생각했는데,, 정말 많은 걸 배우는 문제 였다. 이 문제에 핵심 자체가 사실 재귀로 어떤 문제를 해결하는데에 기본 아이디어 였던 것 같다

결국 제가 생각하는 재귀는 아래와 같습니다.

1. 가장 작은 단위에 작업까지 갔을 때 어떤 역할을 수행하는지 파악.
2. 큰 문제에서 이를 작은 방향 여러 갈래로 분할하는 방법

이렇게 두 가지 아이디어를 통해서 , 큰 문제를 계속해서 여러 갈래로 분할 하고 결국 가장 작은 단위가 됐을 때 그 이후에 어떤 것을 하는지가 재귀 였던 것 같습니다.

고전 문제에서 진짜 배우는게 많다고 사람들이 말했는데 진짜 배운게 많았던 문제 중 하나였던 것 같습니다.