[그래프] SORTGAME Sorting Game

1. 문제

 

중복이 없는 정수 수열에서

 

이 수열의 임의의 구간을 선택

 

해당 구간을 뒤집을 수 있다.

 

=> 뒤집기 연산으로 전체 수열을 정렬하고 싶다.

 

정렬을 위해 뒤집기 연산을 최소 몇번해야 하는지를 계산하여라

 

 

 

 

2. 그래프

 

수열의 길이는 1~8 이다.

 

따라서 이는 최대 8!의 상태가 있는것이다.

 

각각의 상태를 그래프로 표현하고,

 

각각 뒤집기 한번한 연산 결과와 이어주는 간선으로 표현하면

 

그래프가 만들어질 것이다

 

이 그래프를 bfs로  정렬된 상태까지의 거리를 구하면 답이 될것이다

 

 

 

하지만 내가 생각한 그래프를 만드는 방법은

 

수열하나에 번호 하나를 매기고 하나하나 뒤집으며 간선을 이어주는 것 이었다.

 

 

전체 수열 40320 개 중 하나를 뒤집으면 28개의 뒤집어진 수열이 생기고

 

28개를 뒤집는데 2중 반복문에 거기서 또 번호를 달아주는 함수를 통해 인덱스하는 것이다.

 

이 방법은 너무 시간이 오래걸릴꺼 같아서 구현을 그만두었다.

 

 

 

 

3. 책에서의 풀이: 그래프 만들기

 

이 문제를 그래프로 바꿔 표현하는 것은 어렵지 않다.

 

n개를 배열하는 방법에는 n!가 있기 때문에 이를 정점으로하고

 

한 정점에서 한 정점을 만들 수 있다면 간선으로 이어주면 된다.

 

그리고 이를 너비우선 탐색하면된다.

 

 

 

전체를 만들지 않고 그때 그때 주어진 상태에서 bfs로 이어지는 정점을 만들고 나아가

 

정렬된 것을 찾는 방식으로 구현할 수 있지만

 

(이때 책에서는 map을 사용해서 벡터를 키로 삼았다, 즉 내가 생각한 번호를 부여하는 것은 너무 오버헤드였던 것이다.)

 

 

 

이 알고리즘은 느리다.  각 테스트 케이스마다 다시 계산해야하므로 시간 초과될 가능성이 높다.

 

 

이 알고리즘을 최적화하려면 다음 두 가지를 신경써야한다.

 

1. 숫자들이 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다.

 

2. 이 문제의 상태 공간은 양방향 그래프이기 때문에

   시작 정점에서 목표 정점으로 가는 최단 거리는

   목표 정점에서 시작 정점으로 가는 최단 거리와 같다.

   즉 한 배열을 정렬하는 데 드는 연산의 수는

   정렬된 배열을 원래로 바꾸는 데 드는 연산의 수와 같다는 것이다.

 

 

문제의 이 두 가지 속성을 결합하면

 

더 빠른 알고리즘을 만들 수 있다.

 

길이 8인 수열  1234567 을 미리 전처리하여 계산해 두는 것이다.

 

그다음 입력받은 배열을 숫자들의 상대적 크기를 유지하면서 길이 8로 늘리면

 

전처리한 것을 이용하여 따로 연산없이 한번에 알 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
 
using namespace std;
 
 
map<vector<int>, int> distance1;
 
void inputNormalize(int k, vector<int>& input)
{
    vector<int> norm = vector<int>(input);
 
    for(int i = k; i < 8; i++)
        input.push_back(i+1);
 
    sort(norm.begin(), norm.end());
    for(int i = 0; i < k; i++)
    {
        for(int j = 0; j < k; j++)
        {
            if(input[j] == norm[i])
            {
                input[j] = i+1;
            }
        }
    }
    return;
}
 
void makeGraph()
{
    vector<int> seq = {1, 2, 3, 4, 5, 6, 7, 8};
    queue<vector<int> > q;
    q.push(seq);
    distance1[seq] = 0;
    while(!q.empty())
    {
        vector<int> here = q.front();
        q.pop();
        int d = distance1[here];
 
        for(int i = 0; i < 8; i++)
        {
            for(int j = i + 2; j <= 8; j++)
            {
                reverse(here.begin() + i, here.begin() + j);
                if(distance1.count(here) == 0)
                {
                    q.push(here);
                    distance1[here] = d+1;
                }
                reverse(here.begin() + i, here.begin() + j);
 
            }
        }
    }
}
 
 
int main()
{
    makeGraph();
 
    int c;
    cin>>c;
 
    while(c--)
    {
        vector<int> input;
        int k;
        cin>>k;
        for(int i = 0; i < k; i++)
        {
            int a;
            cin>>a;
            input.push_back(a);
        }
        inputNormalize(k, input);
        cout<<distance1[input]<<"\n";
 
    }
}

비트마스크로 푼 풀이

 

SORTGAME

algospot.com :: SORTGAME

- 알고리즘 문제해결전략 887P