[프로그래머스][LV2][C++]하노이의 탑

하노이의 탑은 유명한 재귀 문제이다.

매번 볼때마다 어렵긴하지만 그냥 외우는게 답일 것 같다.

한개만 남아있을 때는 옮겨야하는기둥에 바로 옮기면 되고 

n-1가 남아있을 때는 sub기둥에 n-1를 옮겨두면 된다.

그리고 sub기둥에 있는 것도 end로 하나씩 옮기면 된다.

핵심 코드 

  if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }

전체코드

#include <string>
#include <vector>

using namespace std;
void hanoi(int n,int start,int end,int sub,vector<vector<int>> &answer){
    
    vector<int> v;
    if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }
    
    return;
}


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