[BOJ] 1327 소트 게임

문제

1327번: 소트 게임

홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집어야 한다. 예를 들어, 순열이 5 4 3 2 1 이었고, 여기서 K가 3일 때, 4를 뒤집으면 5 2 3 4 1이 된다. 반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다.

https://www.acmicpc.net/problem/1327

풀이

코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef pair<string, int> psi;
 
string s, t;
int n, k;
char c;
map<string, int> mp;
 
int go() {
    queue<psi> q;
    sort(s.begin(), s.end());
    q.push({s, 0});
    mp[s] = 1;
    while (!q.empty()) {
        string now = q.front().first; int cnt = q.front().second; q.pop();
        if (now == t) return cnt;
        for(int i = 0; i < n-k+1; i++) {
            string tmp = now.substr(i, k), nxt;
            reverse(tmp.begin(), tmp.end());
            nxt = now.substr(0, i) + tmp + now.substr(i+k, now.size());
            if (mp.find(nxt) != mp.end()) continue;
            mp[nxt] = 1;
            q.push({nxt, cnt + 1});
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) {
        scanf(" %c", &c);
        s += c;
    }
    t = s;
    printf("%d", go());
}