Sorting Game (SORTGAME)

algospot.com :: SORTGAME

 

 

BFS, 최단거리

---

처음보는 유형의 문제. 신기한 문제

 

지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데

이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다.

 

1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다.

ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상대적 크기가 같기 때문에 최소 연산 수도 2로 같다.

 

상대적 크기로 변환하기 위해서는 모든 원소를 탐색하면서 자신과 비교하고,

자신보다 작은 원소의 개수가 자신의 상대적 크기라고 할 수 있다.

 

2. 이미 정렬된 배열에서 입력 배열을 만드는 연산횟수와 입력 배열에서 정렬된 배열을 만드는 연산횟수는 같다.

 

위 두가지 개념을 이해하고 순열 벡터를 하나의 객체로 보고 bfs를 진행하면 된다.

 

map<vector<int>, int> 

신기한 조합이다!

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
 
using namespace std;
 
int N;
vector<int> arr;
map<vector<int>, int> toSort;
bool check[9];
 
void precalc() {
    // N개의 숫자를 가진 배열에 대한 연산 횟수들을 구한 적이 있다면 다시 구할 필요가 없다.
    if(check[N]) return;
    check[N] = true;
    
    vector<int> temp(N);
    for (int i = 0; i < N; i++) temp[i] = i;
    
    queue<vector<int> > que;
    que.push(temp);
    toSort[temp] = 0;
    
    while (!que.empty()) {
        vector<int> here = que.front();
        que.pop();
        
        // 현재 순열의 지금까지의 연산 횟수
        int cost = toSort[here];
        for (int i = 0; i < N; i++) {
            for (int j = i + 2; j <= N; j++) {
                // i부터 j-1까지 뒤집는다.
                
                reverse(here.begin() + i, here.begin() + j);
                
                // 뒤집은 순열을 만난적이 없다면 bfs의 특성상 최단거리이므로 해당 순열의 연산횟수를 +1 해준다
                if (toSort.count(here) == 0) {
                    toSort[here] = cost + 1;
                    que.push(here);
                }
                
                // 원상 복구
                reverse(here.begin() + i, here.begin() + j);
            }
        }
    }
}
 
void solve(){
    vector<int> temp(N);
    
    // 주어진 배열의 상대적 크기를 유지하면서 0~N-1 사이의 값으로 변환한다
    for(int i = 0; i < N; i++){
        int cnt = 0;
        for(int j = 0; j < N; j++){
            if(arr[i] > arr[j]){
                cnt++;
            }
        }
        temp[i] = cnt;
    }
    
    
    // 변환된 배열을 통해서 정렬하기까지의 연산 횟수 출력
    cout << toSort[temp] << "\n";
}
 
int main(){
    int test;
    cin >> test;
    while(test--){
        cin >> N;
        arr.resize(N, 0);
        for(int i = 0; i < N; i++){
            cin >> arr[i];
        }
        
        precalc();
        solve();
        
        // toSort.clear();
    }
    
    return 0;
}