[백준 알고리즘/BOJ/C++] 11729 하노이 탑 이동 순서

 

 

재귀하면 생각나는 하노이탑 문제

하노이탑? RGRG 하고 막 풀다가 좀 당황했다ㅎ

 

재귀는 코드를 보고 하나하나 쫓아가면 끝도 없기 때문에

영상으로 어떻게 코딩하는지 보면 이해가 좀 쉬운 것 같다

 

 

아래 영상이 재귀를 다시... 이해하는 데에 많은 도움이 됐다 (개념설명X 푸는과정O)

www.youtube.com/watch?v=AogMbfRwguk

 

 

#include <iostream>
using namespace std;
 
void move(int n, int from, int to) {
    int middle = 6 - from - to;
 
    if (n == 1) {
        cout << from << ' ' << to << "\n";
        return;
    }
    else if (n >= 2) {
        move(n - 1, from, middle); //위에 넘들이 from과 to 빼고 가운데로
        move(1, from, to); //가장 밑판
        move(n - 1, middle, to);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int k;
 
    cin >> k;
    //이동 횟수 2^k-1 (= 1<<k)
    cout << (1 << k) - 1 << "\n";
    move(k, 1, 3);
}