[알고스팟] SORTGAME - Sorting Game (C++, BFS)

문제

 

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

algospot.com :: SORTGAME

 

풀이

 

종만북 난이도: 중

 

BFS문제들은 2차원 좌표상에서 이동하는 문제가 많은데 이번 문제는 전혀 다른 BFS 적용 문제라 신선했다.

(그리고 어려웠다...)

 

1 2 3 4 수열의 구간들이 반전되어 나타나는 수열은 다음과 같이 그래프로 표현이 가능하다.

각 노드들은 1 2 3 4에서 한 구간 만을 반전시킨 것이므로 1번의 뒤집기 연산으로 이동이 가능하다.

각 노드들도 각각의 구간을 반전시킨 서브 트리를 가지고 이는 1 2 3 4에서 2번의 뒤집기 연산으로 이동 가능하다.

 

단 중복된 수열이 등장할 수 있다.

예를 들어 1 2 3 4에서 1 2 를 반전시켜 2 1 3 4를 만들었지만 

2 1 3 4에서 2 1을 반전시키면 다시 1 2 3 4가 된다.

따라서 2회의 연산이 소모되지만 1 2 3 4를 만드는 데는 0번의 연산만으로도 충분하다.

 

중복을 제거할 때는 다이나믹 프로그래밍을 사용하자.

이러한 수열도 DP로 구현하기 위해 배열도 key값으로 이용 가능한 map 자료구조를 이용하자.

map<vector<int>, int(연산 횟수 저장)> precal;

 

 

하지만 이번 문제에서 중요한 점은 테스트 케이스 수가 최대 1000회이라는 점이다.

각각의 배열을 모두 새로 BFS 통해 계산한다면 시간 초과가 발생한다.

따라서 모든 테스트 케이스에서 이용 가능하도록 입력받는 모든 배열을 수의 크기 순서대로 변경하자.

예를 들어 10 50 12 1은 상대적 크기 순서대로 나타내면 2 4 3 1이 된다.

 

이런 식으로 입력 배열 값을 변경하는 함수는 다음과 같이 구현했다.

 

vector<int> CompressArr(vector<pair<int,int>>& arr){
  sort(arr.begin(), arr.end());
 
  vector<int> ret(arr.size());
  for(int i=0; i<arr.size() ; ++i)
    ret[arr[i].second] = i+1;
 
  return ret;
}

 

 

이제 모든 배열은 배열의 크기를 arr_size라 하면

1~arr_size까지의 수로만 나타난다.

 

모든 배열이 정렬된 배열로 변환되는 cost는 정렬된 배열이 입력된 배열로 변환되는 cost와 동일하다.

(양방향 그래프에서 역방향으로 진행할 뿐이므로 )

따라서 1~8까지의 배열 크기들을 모두 미리 정렬된 배열에서의 변환된 배열로의 최소 연산 횟수를 map에 저장하자.

 

map<vector<int>, int> precal;
 
void SortGame(int arr_size){
  vector<int> arr(arr_size);
 
  for(int i=0; i<arr_size ; ++i)
    arr[i] = i+1;
  
  precal[arr] = 0;
  queue<vector<int>> que;
  que.push(arr);
 
  int cnt=0;
  while(!que.empty()){
    vector<int> temp = que.front();
    que.pop();
 
    int cost = precal[temp];
    for(int i =0 ; i<arr_size ; ++i){
      for(int j=i+2; j<=arr_size ; ++j){
        reverse(temp.begin()+i, temp.begin()+j);
 
        if(precal.count(temp) == 0){
          precal[temp] = cost +1;
          que.push(temp);
        }
        reverse(temp.begin()+i, temp.begin()+j);
      }
    }
 
  }
}

 

이제 모든 테스트 케이스에서 동일한 map의 저장 값을 사용 가능하므로 시간을 단축시킬 수 있다.

 

 

코드