하노이 탑 이동 순서

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// 하노의 탑의 sum에 대한 점화식은 (2^n - 1) 이다
int sum=0;
vector<pair<int,int>> ans;
void Hanoi(int s, int e ,int n){
    if(n == 0) return;
    else{
        /* 1) s지점부터 (6-s-e)지점까지 n-1개의 원판을 이동 */
        Hanoi(s, 6-s-e, n-1); 
        /* 2) s에 있는 1개의 원판을 e로 이동하는 것 */
        sum++;
        ans.push_back({s,e}); 
        /* 3) (6-s-e)로 옮겼던 원판 n-1개를 e로 옮기는 작업 */
        Hanoi(6-s-e, e, n-1); 
        return;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int K;
    cin >> K;
    Hanoi(1, 3, K);
    cout << sum << '\n';
    // cout << (1<<K) << '\n'; 
    for(int i=0;i<ans.size();i++) cout << ans[i].first << ' ' << ans[i].second <<'\n';
    return 0;
}

• 핵심 :하노이의 탑 풀이에 필요한 과정을 찾기
  1) 가장 큰 원반 n을 제외한 n-1개의 원판을 나머지 기둥(2기둥)으로 이동
  2) 원판 n을 3기둥으로 이동
  3) 원판 n-1개를 2기둥에서 3기둥으로 이동

• key point!
  : 원판을 옮기는 과정을 재귀로 풀어낼 때 움직이는 기둥의 정보도 함께 필요!