Sorting Game 29장 SORTGAME

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<random>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
 
map<vector<int>, int > toSort;
//[0,...,n-1]의 모든 순열에 대해 toSort[]를 계산해 저장한다.
void precalc(int n) {
    vector<int> perm(n);
    for (int i = 0; i < n; i++) perm[i] = i;
    queue<vector<int> > q;
    q.push(perm);
    toSort[perm] = 0;
    while (!q.empty()) {
        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) {
    //perm 을 [0,....,n-1]의 순열로 변환한다.
    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 bfs(const vector<int>& perm) {
    int n = perm.size();
    //목표 정점을 미리 계산한다.
    vector<int> sorted = perm;
    sort(sorted.begin(), sorted.end());
    //방문 목록(큐)과 시작점부터 각 정점까지의 거리
    queue<vector<int> > q;
    map<vector<int>, int > distance;
    //시작점을 큐에 넣는다.
    distance[perm] = 0;
    q.push(perm);
    while (!q.empty()) {
        vector<int> here = q.front();
        q.pop();
        //목표 정점을 발견했으면 곧장 종료한다.
        if (here == sorted) return distance[here];
        int cost = distance[here];
        //가능한 모든 부분 구간을 뒤집어본다.
        for (int i = 0; i < n; i++) {
            // reverse는 원하는 주소 +1을 해줌.열려있다.
            for (int j = i + 2; j <= n; j++) {
                reverse(here.begin() + i, here.begin() + j);
                if (distance.count(here) == 0) {
                    distance[here] = cost + 1;
                    q.push(here);
                }
                reverse(here.begin() + i, here.begin() + j);
            }
        }
    }
    //oops
    return -1;
}
 
int main(void) {
    int cases;
    cin >> cases;
    while (cases--) {
        toSort.clear();
        int N;
        cin >> N;
        vector<int> arr(N, 0);
        for (int i = 0; i < N; i++)
            cin >> arr[i];
        precalc(N);
        cout << solve(arr) << endl;
 
    }
    return 0;
}

문제출처https://algospot.com/judge/problem/read/SORTGAME

함수 bfs를 사용해서 문제를 풀면 map에 접근하는데 드는 시간이 크기 때문에 solve함수를 이용해서 최적화한다.

문제를 푸는 핵심은

1.한 배열을 정렬하는 데 드는 연산의 수는 정렬된 배열을 원래 배열로 바꾸는데 드는 연산의 수와 같다!

2.숫자들이 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다!

p.s. 이상하게 배열크기가 7이상만 되면 코드가 실행이 안되네요 너무 느려져서 그런건지 사이트채점은

정답으로 나오는데 이상하네요.