(C++) - 프로그래머스(연습문제) : 하노이의 탑

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

코딩테스트 연습 - 하노이의 탑

재귀 구현 문제였습니다.

 

풀이방법

 반복되는 행동을 찾아냅니다. 반복되는 행동이란 특정 규칙 하나만으로 취하는 행동을 뜻합니다. 

반복되는 행동은 다음과 같습니다.

1->2로 n-1개의 원판을 옮깁니다. 1에는 가장큰 n번째 원판만 남게됩니다.

1->3으로 가장 큰 n번째 원판을 옮깁니다.

2->3으로 n-1개의 원판을 옮깁니다.

 

Code

#include <vector>

using namespace std;
vector<vector<int>> ans;
void hanoi(int from, int mid, int to, int n){
    if(!n) {return;}
    //1 -> 2로 n-1개 원판 옮김
    //1 -> 3로 남은 한 개(가장 큰 원판) 옮김
    //2 -> 3로 n-1개 원판 옮김
    hanoi(from,to,mid,n-1);
    ans.push_back({from,to});
    hanoi(mid,from,to,n-1);
}

vector<vector<int>> solution(int n) {
    for(auto a : ans) a.clear();
    hanoi(1,2,3,n);
    return ans;
}