[프로그래머스 2레벨] 하노이의 탑 (C++)

#include <string>
#include <vector>

using namespace std;

void hanoi(int n, int go, int to, vector<vector<int>>&v)
{
    if(n==1) //원판이 1개인 경우 (성공 케이스)
    {
        v.push_back({go, to});
        return;
    }
    
    hanoi(n-1, go, 6-go-to, v); //n-1개의 원판을 보조(중간) 기둥으로 옮김 
    hanoi(1, go, to, v); //가장 큰 원판을 목표 기둥으로 옮김
    hanoi(n-1, 6-go-to, to, v); //n-1개의 원판을 보조(중간) 기둥에서 목표 기둥으로 이동
}

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

 

상당히 유명한 하노이의 탑 재귀 문제이다.

문제에서 기둥이 3개로 고정되어있으므로, 이를 숫자로 합치면 1+2+3 = 6이다.

따라서 보조(중간) 기둥에 대해 6-go-to로 설정할 수 있다.

 

재귀 순서는 n-1개를 보조(중간) 기둥으로 옮기고, 가장 큰 원판 (1개) 를 목표 기둥으로 옮긴다.

그리고 이제 다시 n-1개의 원판을 목표 기둥으로 옮겨주면 된다.

 

재귀를 돌면서 n==1이 되는 순간 케이스가 정해져 있으므로 (go -> to) 해당 케이스를 담아주고 리턴해준다.