배열 스왑해서 정렬하기 (BFS 응용)

#include "stdafx.h"
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
 
using namespace std;
 
void makeBFS(int n,map<vector<int>,int> & data) {
    // make buffere queue and starting point
    vector<int> perm(n);
    for (int i = 0; i < n; i++) {
        perm[i] = i;
    }
    int flag = 0;
    long long count = 0;
    queue<pair<vector<int>,int>> buffer;
    buffer.push(pair<vector<int>,int>(perm,0));
    data.insert(pair<vector<int>, int>(perm, 0));
    while (buffer.size() != 0) {
        count++;
        if (count % 500 == 0) cout << "running at " << count << endl;
        vector<int> curr = buffer.front().first;
        int dis = buffer.front().second;
        buffer.pop();
        // make all combinations and put in map
        vector<int> tmp;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                tmp = curr;
                reverse(tmp.begin() + i, tmp.begin() + j + 1);
                if (data.find(tmp) == data.end()) {
                    if (flag < dis) {
                        cout << "current at " << dis << endl;
                        flag++;
                    }
                    data.insert(pair<vector<int>, int>(tmp, dis + 1));
                    buffer.push(pair<vector<int>, int>(tmp, dis + 1));
                }
            }
        }
    }
}
 
void swap(int & a, int & b) {
    int tmp = a;
    a = b;
    b = tmp;
}
 
int findminswaps(vector<int> & data) {
    map<vector<int>, int> buf;
    // rescale data to 0 ... n-1
    for (int i = 0; i < data.size(); i++) {
        int smaller = 0;
        for (int j = 0; j < data.size(); j++) {
            if (data[i] > data[j]) smaller++;
        }
        data[i] = smaller;
    }
    for (int x : data) cout << x << " ";
    cout << endl;
    // make BFS
    makeBFS(data.size(), buf);
    // find min distance
    auto it = buf.find(data);
    if (it == buf.end()) return -9999;
    return it->second;
}
 
map<vector<int>, int> toSort;
 
void precalc(int n) {
    vector<int> perm(n);
    for (int i = 0; i < n; ++i) {
        perm[i];
    }
    queue<vector<int>> q;
    q.push(perm);
    toSort[perm] = 0;
    int count = 0;
    while (!q.empty()) {
        count++;
        if (count % 500 == 0) cout << "count at : " << count << endl;
        vector<int> here = q.front();
        q.pop();
        int cost = toSort[here];
        for (int i = 0; i < n; ++i) {
            for (int j = i + 2; j <= n; j++) {
                reverse(here.begin() + i, here.begin() + j);
                if (toSort.count(here)==0) {
                    toSort[here] = cost + 1;
                    q.push(here);
                }
                reverse(here.begin() + i, here.begin() + j);
            }
        }
    }
}
 
int solve(const vector<int> & perm) {
    int n = perm.size();
    vector<int> fixed(n);
    for (int i = 0; i < n; ++i) {
        int smaller = 0;
        for (int j = 0; j < n; ++j) {
            if (perm[j] < perm[i])
                ++smaller;
        }
        fixed[i] = smaller;
    }
    return toSort[fixed];
}
 
int main() {
    map<vector<int>, int> tmp;
    vector<int> v1 = { 1,2,3,4,8,7,6,5 };
    precalc(8);
    cout << solve(v1) << endl;
    //cout << findminswaps(v1) << endl;
    while(1){}
    return 0;
}