[백준] 1327 소트게임 (C++)

링크: https://www.acmicpc.net/problem/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을 출력한다.

---

풀이

좌표가 아닌 순열에서 BFS를 적용하는 문제이다.

순열이 주어졌을 때 뒤집을 수 있는 경우의 수들을 큐에 추가하고,

중복을 방지하기 위해 해시맵에 순열을 추가하여 관리하여 문제를 풀면 된다.

그리고 순열을 문자열로 저장하면 더욱 쉽게 문제를 풀 수 있다.

코드

#include <iostream>
#include <map>
#include <queue>
using namespace std;

string nums = "";
map<string, bool> numMap;
string answer = "";

int solve(int n, int k){
    queue<string> que;
    que.push(nums);
    numMap[nums] = true;
    int cnt = 0;

    while (!que.empty()){
        int size = que.size();
        for (int i = 0; i < size; i++){
            string str = que.front();
            que.pop();

            if (str == answer){
                return cnt;
            }

            for (int j = 0; j <= n-k; j++){
                string tmp = "";
                for (int l = 0; l < j; l++){
                    tmp += str[l];
                }
                for (int l = j+k-1; l >= j; l--){
                    tmp += str[l];
                }
                for (int l = j+k; l < n; l++){
                    tmp += str[l];
                }
                if (!numMap[tmp]){
                    numMap[tmp] = true;
                    que.push(tmp);
                }
            }
        }
        cnt++;
    }
    return -1;
}

int main(){
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++){
        char num;
        cin >> num;
        nums += num;
        answer += (i+1)+'0';
    }

    cout << solve(n, k);
}