Level 2. 하노이의 탑

Level 2. 하노이의 탑

 

 

유명하고 전형적인 하노이의 탑 알고리즘이다.

 

3개를 A에서 B를 거쳐 C로 옮긴다고 할 때,

1. A에 있는 2개를 C를 거쳐 B로 옮긴다.
2. A에 남은 1개를 C로 옮긴다.
3. 1단계에서 B로 옮겼던 2개를 A를 거쳐 C로 옮긴다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> solution(int n, int from, int through, int to)
{
    if (n == 1)
        return {{from, to}};

    vector<vector<int>> result = solution(n - 1, from, to, through);

    result.emplace_back(vector<int>{from, to});

    vector<vector<int>> t = solution(n - 1, through, from, to);
    copy(t.begin(), t.end(), back_inserter(result));

    return result;
}

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