[백준] 1327

소트 게임

문제

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

입력으로 들어온 순열을 오름차순으로 만들려고 한다. 게임을 최대한 빨리 끝내고 싶을 때, 수를 최소 몇 개 선택해야 하는지 구해보자.

입력

첫째 줄에 순열의 크기 N과 K가 주어진다. 둘째 줄에 순열에 들어가는 수가 주어진다.

출력

첫째 줄에 정답을 출력한다. 만약 오름차순으로 만들 수 없으면 -1을 출력한다.

풀이

#include <iostream>
#include <map>
#include <string>
#include <queue>
#include <algorithm>

int n, k;
std::string str;
std::string sorted_str;
std::queue<std::pair<std::string, int> > que;
std::map<std::string, int> map;

int bfs() {
    std::string current;
    int cnt;
    que.push(std::make_pair(str, 0));

    while (!que.empty()) {
        current = que.front().first;
        cnt = que.front().second;
        que.pop();

        if (current == sorted_str) return cnt;
        if (map.find(current) != map.end()) continue;
        map.insert(std::make_pair(current, 1));
        for (int i = 0; i <= n - k; i++) {
            std::string substr = current.substr(i, k);
            std::reverse(substr.begin(), substr.end());
            substr = current.substr(0, i) + substr + current.substr(i + k, n - k);
            que.push(std::make_pair(substr, cnt + 1));
        }
    }
    return -1;
}

int main(void) {
    std::map<char, int> mp;
    char temp;

    std::cin >> n >> k;

    for (int i = 0; i < n; i++) {
        std::cin >> temp;
        str += temp;
        mp.insert(std::make_pair(temp, 0));
    }

    for (std::map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
        sorted_str += it->first;
    }

    std::cout << bfs();
}

반성회

사실상의 브루트포스랑 비슷한데 BFS처럼 큐에 넣어서 돌리고 해당 문자열을 방문했는지 여부를 맵에다 체크하는 방식…