[재귀][프로그래머스] 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

 

 

 

[알고리즘]

1. n-1 개의 원판을 목적지가 아닌 기둥으로 옮긴다.

2. 가장 마지막 원판을 목적지 기둥으로 옮긴다

3. 다른 기둥에 있던 n-1개의 원판을 목적지 기둥으로 옮긴다

 

이때 n이 1로 전달되는 경우 그냥 바로 목적지로 가면 되니까 예외처리도 해준다

 

#include <string>
#include <vector>

using namespace std;
std::vector<std::vector<int>> answer;
void Hanoi(int n, int from, int dest, int tmp) {
    if (n == 1) {
        answer.push_back({from, dest});
    } else {
    	// n-1 개의 원판을 목적지가 아닌 기둥으로 옮기기
        Hanoi(n-1, from, tmp, dest);
        
        // 마지막 원판을 목적지로 이동시키기
        answer.push_back({from, dest});
        
        // 나머지 tmp 기둥에 있던 N-1개 원판을 목적지로 옮기기
        Hanoi(n-1, tmp, dest, from);
    }
}



vector<vector<int>> solution(int n) {
    Hanoi(n, 1, 3, 2);
    return answer;
}