Algorithm/알고스팟

algospot - sortgame

jhg0406 2020. 1. 10. 17:26

 

시작 수열을 최소한 reverse해 정렬된 수열을 만드는것은 

가능한 수열들을 정점으로 하고, 특정 수열에서 reverse를 했을때 만들어 질수 있는 수열들을 간선으로 연결한 그래프에서 시작정점(시작수열) 에서 목적지정점(정렬된수열) 까지의 최단거리를 구하는것과 같습니다.

따라서 그래프를 만들고, BFS를 사용하면 문제를 해결할수 있습니다.

 

 

 

 

 

https://algospot.com/judge/problem/read/SORTGAME

 

algospot.com :: SORTGAME

Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면

algospot.com

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//algospot - sorting game
 
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
 
map<vector<int>, int> cost;
 
void precalc()
{
    queue<vector<int>> q;
    vector<int> v(8);
    for (int i = 0; i < 8; i++)
        v[i] = i;
    cost[v] = 0;
    q.push(v);
    int c;
 
    while (!q.empty())
    {
        v = q.front();
        q.pop();
        c = cost[v];
        for (int i = 0; i < 7; i++)
        {
            for (int j = i + 2; j < 9; j++)
            {
                reverse(v.begin() + i, v.begin() + j);
                if (cost.count(v) == 0)
                {
                    q.push(v);
                    cost[v] = c + 1;
                }
                reverse(v.begin() + i, v.begin() + j);
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int C, N;
    cin >> C;
    vector<int> v(8);
    priority_queue<pair<int, int>> pq;
    precalc();
 
    for (int t_num = 0; t_num < C; t_num++)
    {
        cin >> N;
        int x;
        for(int i = 0; i<N; i++)
        {
            cin >> x;
            pq.push(make_pair(-1*x, i));
        }
 
        for(int i = 0; i<N; i++)
        {
            x = pq.top().second; pq.pop();
            v[x] = i;
        }
        for(int i = N; i<8; i++) v[i] = i;
        cout << cost[v] << "\n";
    }
}
 cs