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

문제 링크

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

1327번: 소트 게임

 

---

◆문제 해결 및 설명◆

문제 해설 : 순열을 일정길이만큼만 뒤집을 수 있을 때, 최소 몇 번 만에 오름차순으로 만들 수 있는가

 

우선 순열이 최대 8의 길이를 가지기 때문에 브루트포스를 통해서 풀 수 있겠다는 생각이 들었다.

순열을 뒤집어야 하는데, string의 reverse()를 사용하면 편하여 string으로 input을 받아주었다.

 

알고리즘은 BFS로 구현을 하였으며,  모든 순열을 저장(방문처리)할 맵<string,int>을 선언하고, 순열이 적합한지 차례대로 확인하기 위해서 큐<string,int>를 선언하였다.

 

정렬된 순열 string변수 target을 준비하여 target과 같다면 회전시킨 횟수를 return 하고,

target과 같지 않으면서 맵(방문처리)에 없다면, 맵에 true를 설정해 주고 모든 위치에서 뒤집은 순열(string, cnt+1)을 큐에 집어넣고 target과 비교부터 반복한다.

 

while문이 끝날 때까지 못 찾는다면 -1을 리턴해준다.

 

브루트포스를 통해 만들어낸 값을 unordered_map을 통해서 방문처리를 한다는 것이 중요한 개념이라는 것을 느끼게 한 문제였다.

 

◆코드 전문◆

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

using namespace std;
int K, N;

int bfs(string str)
{
    queue<pair<string, int>> que;
    que.push({str, 0});
    unordered_map<string, bool> visited;
    string target = str;
    sort(target.begin(), target.end());

    while (!que.empty())
    {
        string curent = que.front().first;
        int cnt = que.front().second;
        que.pop();

        if (curent == target)
        {
            return cnt;
        }
        if (!visited.count(curent))
        {
            visited[curent] = true;
            for (int j = 0; j <= N - K; j++)
            {
                string temp = curent.substr(j, K);
                reverse(temp.begin(), temp.end());
                que.push({curent.substr(0, j) + temp + curent.substr(j + K, curent.size()), cnt + 1});
            }
        }
    }
    return -1;
}

int main()
{
    cin >> N >> K;

    cin.ignore();
    string str;
    getline(cin, str);

    while (str.find(' ') != str.npos)
    {
        str.erase(str.find(' '), 1);
    }
    cout << bfs(str);
}