2-1. 자료구조 [BOJ 1327번]

1. 관련 문제 🎯

문제 : 백준 1327 소트 게임 🎮
난이도 : 골드 5

2. 문제 소개 🧩

1️⃣ 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다.
2️⃣ 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집어야 한다.
3️⃣ 반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다. (2 ≤ K ≤ N ≤ 8)
4️⃣ 입력으로 들어온 순열을 오름차순으로 만들려고 한다.
5️⃣ 게임을 최대한 빨리 끝내고 싶을 때, 수를 최소 몇 개 선택해야 하는지 구해보자.

• 아래의 예시는 "5 4 3 2 1" 총 5개의 숫자가 주어졌을 때, 만약 4를 뒤집으면 K=3이므로 4,3,2를 뒤집은 2,3,4를 5와 1의 사이에 넣어주게 된다.
  이처럼, 계속해서 뒤집어서 처음에 주어진 5,4,3,2,1을 1,2,3,4,5로 만드는 최소의 선택의 수를 구하는 것이 이번 문제의 목적이다!!
  

3. 문제 풀이 🖌️

KEY POINT
1) 입력받은 문자열 중에서 하나씩 선택하여 K개의 수를 뒤집어 보면서, 오름차순이 되는 경우가 있는지를 확인해본다.
2) 이때, 최소의 개수를 선택하는지를 확인해야 하므로 BFS를 사용하여 살펴본다.
3) 그리고 Map을 사용하여 이미 해당 문자열 방문 여부를 표시해준다.

• 이전에 해당 문자열과 동일한 문자열을 방문한 경우, 최소 방문이기 때문에 해당 문자열은 최소를 만족하지 않아서 더이상 탐색을 하지 않아도 된다.

3-1. 숫자를 입력받는다.

이때, 중요한 점은 숫자를 문자열로 입력받는다는 점이다!! 🔥
왜냐하면, 숫자를 문자열로 입력받으면 substr()함수를 사용하여 원하는 문자열의 길이만큼 잘라서 reverse()함수로 뒤집을 수 있기 때문이다!!

char nums;
string numbers;

for(int i=0; i<N; i++){
	cin >> nums;
    numbers += nums;
}

3-2. 구하고자 하는 오름차순 정렬을 구해놓는다.

• BFS를 돌면서 오름차순 정렬이 된 문자열과 동일할 경우 break로 while문을 나와야하기 때문이다!

string origin_numbers;
origin_numbers = numbers;
sort(numbers.begin(), numbers.end());   //구하고자 하는 오름차순 정렬

3-3. BFS를 사용하여 모든 문자열의 경우의 수를 살펴본다!

• 이때, 하나의 문자열을 3가지의 문자열로 나누어볼 수 있다.
  1) 뒤집을 문자열 전의 문자열 = num1 -> 0번째 ~(i-1)번째
  2) 뒤집을 문자열 = num2 -> i번째~(i+K-1)번째
  3) 뒤집을 문자열 후의 문자열 = num3 -> k+i번째 ~ (k+i+N-1)번째
  

for(int i=0; i<=N-K; i++){
     string num1 = here.substr(0,i);
     string num2 = here.substr(i, K);
     reverse(num2.begin(), num2.end());
     string num3 = here.substr(K+i,N);
     que.push({num1+num2+num3,depth+1});
}

• map<string,bool> map1을 선언하여 해당 문자열의 방문 여부를 체크한다.
• 그리고 queue<pair<string,int>> que로 선언하여 새로운 문자열과 depth 해당 문자열의 깊이를 저장해준다. depth가 뒤집은 횟수를 의미하기 때문에 만약 문자열이 구하고자 하는 오름차순 문자열인 경우, 해당 문자열의 깊이가 구하고자 하는 답이 된다!!

map<string, bool> map1;
queue<pair<string,int>> que;
que.push({origin_numbers,0});

 while(!que.empty()){
        string here = que.front().first;
        int depth = que.front().second;

        if(here == numbers){
            ans = depth;
            break;
        }
        que.pop();

        if(map1[here] != true){
            for(int i=0; i<=N-K; i++){
                string num1 = here.substr(0,i);
                string num2 = here.substr(i, K);
                reverse(num2.begin(), num2.end());
                string num3 = here.substr(K+i,N);
                que.push({num1+num2+num3,depth+1});
            }
            map1[here] = true;
        }
}

4. 전체 코드 🔑

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

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

    int N = 0, K =0;
    char nums;
    string numbers;
    string origin_numbers;
    map<string, bool> map1;
    int ans = -1;
    cin>>N>>K;
    
    for(int i=0; i<N; i++){
        cin >> nums;
        numbers += nums;
    }

    origin_numbers = numbers;
    sort(numbers.begin(), numbers.end());   //구하고자 하는 오름차순 정렬
    
    queue<pair<string,int>> que;
    que.push({origin_numbers,0});

    while(!que.empty()){
        string here = que.front().first;
        int depth = que.front().second;

        if(here == numbers){
            ans = depth;
            break;
        }
        que.pop();

        if(map1[here] != true){
            for(int i=0; i<=N-K; i++){
                string num1 = here.substr(0,i);
                string num2 = here.substr(i, K);
                reverse(num2.begin(), num2.end());
                string num3 = here.substr(K+i,N);
                que.push({num1+num2+num3,depth+1});
            }
            map1[here] = true;
        }
    }

    cout<<ans<<"\n";
}

5. 결과 🏆