[정올] 1316 / 정렬게임

모든 경우의 수를 다 bfs 하면 된다. set을 사용해 중복을 방지하자.

// Preset 생략

set<string> used;

string rev(string str, int f, int t) {
    reverse(str.begin() + f, str.begin() + t + 1);
    return str;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    if (n == 1)
    {
        cin >> n;
        cout << 0;
        return 0;
    }

    if (n == 2)
    {
        int x;
        cin >> n >> x;
        if (n > x)
            cout << 1;
        else
            cout << 0;
        return 0;
    }

    string nu;
    vector<pair<int, int>> gs;
    string ans = "";

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        gs.push_back({x,i});
        ans += i + '1';
    }
    
    sort(gs.begin(),gs.end(), [](const pii a, const pii b) {
        return a.first < b.first;
    });
    
    for(auto x : gs) nu += x.second + 1 + '0';

    queue<string> q;
    unsigned long step = 0;
    
    q.push(nu);
    // cout << "ANS IS " << ans << "\n";
    while(true) {
        unsigned long qs = q.size();
        while (qs--) {
            string qf = q.front();
            q.pop();
            
            if(qf == ans) {
                cout << step;
                return 0;
            }
            
            for(int i = 0;i < n;i++) {
                for(int j = i + 1;j < n;j++) {
                    string reved = rev(qf, i, j);
                    if(used.find(reved) != used.end()) continue;
                    // cout << "REV " << i << " , " << j << " / " << reved << "\n";
                    used.insert(reved);
                    q.push(reved);
                }
            }
        }
        step++;
    }
}