프로그래머스 하노이의 탑 c++ // 재귀함수

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

프로그래머스

특징 : n==1일때만 answer에 푸쉬함.

나머지는 추상적으로 정의함.

 

기둥번호 : 1, 2, 3번

기둥번호 : a번,  6-a-b번, b번

할일(재귀식) :

1. a에서 6-a-b기둥으로 n-1개옮기기

2. a에서 b로 1개 옮기기

3.6-a-b에서 b로 n-1개 옮기기

 

n==1일때만 base condition처리.

임의(k개)일때는 재귀적으로 처리후

도미노가 쓰러지듯 알아서 처리된다.

 

#include <bits/stdc++.h>

using namespace std;

//기둥a에서 기둥b로 원판n개 옮기는함수
//특징 : n==1일때만 answer에 푸쉬함.
void func(int a, int b, int n, vector<vector<int>>& answer){
    
    //base condition
    if(n==1){
        answer.push_back({a,b});
        //cout<<a<<" "<<b<<" 개수: "<<n<<"\n";
        return;
    }
    func(a,6-a-b,n-1,answer);   //a에서 6-a-b기둥으로 n-1개 옮기기
    //cout<<a<<" "<<b<<" 개수: "<<n<<"\n";
    answer.push_back({a,b});    //a에서 b기둥으로 1개 제일큰원판 옮기기
    func(6-a-b,b,n-1,answer);   //6-a-b에서 b기둥으로 n-1개 옮기기
    
    
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    
    func(1,3,n,answer);

    return answer;
}