[프로그래머스]연습문제 : 하노이의 탑 (level 3) (c++)

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

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

 

분할 정복

#include <string>
#include <vector>

using namespace std;

void move_tower(vector<vector<int>>& answer, int n, int from, int to)
{
    if (n == 0)
    {
        return;
    }

    // 1 ~ N -1 탑 이동 : from -> mid (to 경유)
    move_tower(answer, n - 1, from, 6 - from - to);

    // 마지막 원판 : from -> to 이동
    answer.push_back({ from, to });

    // 1 ~ N -1 탑 이동 : mid -> to (from 경유)
    move_tower(answer, n - 1, 6 - from - to, to);
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;

    // 하노이탑 이동 : 1번 -> 3번 (2번 경유)
    move_tower(answer, n, 1, 3);

    return answer;
}

 

 

자세한 풀이는 BOJ하노이탑 문제 설명에 ㅎㅎ