[프로그래머스] 하노이의 탑 C++ 문제풀이

문제 풀이

하노이의 탑 문제는 n개의 원판을 1번 기둥에서 3번 기둥으로 옮기는 문제이다.

n개의 원판을 (1 -> 3)으로 이동하려면

n-1개의 원판을 (1 -> 2) 로 옮기고, 마지막 원판을 (1->3) ,n-1개 원판을 (2->3)으로 옮기면 된다.

위 처럼 진행 되는 문제이다!

이를 재귀를 통해서 n == 1 일 때 까지 반복해서 풀면 된다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> answer;

void hanoi(int start, int end, int target, int cnt){
    if(cnt == 1){
        answer.push_back({start, target}); 
    }
    else{
        hanoi(start, end, 6 - (start+target), cnt-1);
        answer.push_back({start, target}); 
        hanoi(6 - (start+target), end, target, cnt - 1);
    }
}

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