소트 게임

BOJ 소트 게임
SOL)

BFS 어떤 순열과  이 순열에서 만들 수 있는 새로운 순열사이 간선이 연결된
Graph라 생각하고 문제를 푼다.

[-] Collapse

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
map<vector<int>, int> visit;
vector<int> arr, goal;
int N, K;

int BFS(){
    int cost = 0;
    queue<vector<int> > q;
    q.push(arr);
    visit[arr]++;
    while (!q.empty()){
        int size = q.size();
        for (int l = 0; l < size; l++){
            vector<int> mv = q.front();
            q.pop();
            if (mv == goal) return cost;
            for (int i = 0; i <= N - K; i++){
                reverse(mv.begin() + i, mv.begin() + i + K);
                if (visit.count(mv) == 0){
                    visit[mv]++;
                    q.push(mv);
                }
                reverse(mv.begin() + i, mv.begin() + i + K);
            }
        }
        cost++;
    }
    return -1;
}

int main(){
    scanf("%d%d", &N, &K);
    arr = vector<int>(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    goal = arr;
    sort(goal.begin(), goal.end());
    printf("%d", BFS());
}