1327번

1327번 - 소트 게임

BFS로 문제를 풀었다, 예전에 3x3 짜리 비트마스크 문제랑 유사하다고 느껴졌다.

N의 값이 작기도 하고, int 형으로 구하기 귀찮아서 string 과 map 을 이용해서 문제를 풀었다.

map 을 평소 BFS에서 dist 배열과 visited 배열을 섞은 것처럼 사용하였다.

목표값과 시작값을 정해놓고 BFS를 돌리면서 목표값이 나오면 while 문을 빠져나오도록 했다

또 change 함수에서는 특정문자와, 특정 위치를 인자로 받고, 그 부분만을 reverse 해서 string 값을 반환하도록 만들었다.

그리고 만약 값이 존재하지 않는다면 -1을 출력하도록 하였다.

비트 마스크로 푸는 방법을 알아봐야 겠다.

<정답 코드>

#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
int n, k;
string change(string now,int t)
{
    string ret = "";
 
    for (int i = t; i < t+k; i++)
    {
        ret += now[i];
    }
 
    reverse(ret.begin(), ret.end());
 
    for (int i = t; i < t+k; i++)
    {
        now[i] = ret[i - t];
    }
 
    return now;
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    
    cin >> n >> k;
    vector<int> v(n);
    string sum = "";
    string goal = "";
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        sum += v[i] + '0';
        goal += (i + 1) + '0';
    }
 
    map<string, int> m;
    queue<string> q;
    q.push(sum);
    m[sum] = 0;
 
    while (!q.empty())
    {
        string now = q.front();
        q.pop();
 
        if (now == goal)
        {
            break;
        }
 
        for (int i = 0; i < n - k + 1; i++)
        {
            string next = change(now, i);
 
            if (m.count(next) == 0)
            {
                m[next] = m[now] + 1;
                q.push(next);
            }
        }
    }
 
    if (m.count(goal) == 0)
    {
        cout << "-1\n";
    }
    else
    {
        cout << m[goal] << "\n";
    }
 
    return 0;
}