[알고스팟/c++] Sorting Game SORTGAME 문제 풀이

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

algospot.com :: SORTGAME

오늘은 "알고리즘 문제해결전략"에서 너비 우선 탐색(BFS)에 대해서 공부했다. 책에서는 너비 우선 탐색은 깊이 우선 탐색과 달리 주로 그래프의 최단 경로 문제를 풀기 위해 사용된다고 나와있다. 

그 이유는 BFS는 정점에 인접한 거리에 있는 정점들을 우선적으로 방문하기 때문이지 않을까 싶다.

 

예를 들어, 우선적으로 바로 인접한 정점들(정점과 정점 사이의 간선이 1개)을 방문하고, 그 다음부터는 정점과 정점 사이에 있는 간선의 개수가 2개인 정점들을 방문하고, 그 다음 3개 ...  이런 식이다. 

 

접근 방식

---

1. 이 문제를 왜 BFS를 통해 풀 수 있지?에 대한 고민이 우선적으로 필요했다. 일단 주어진 수열을 뒤집어서 오름차순으로 정렬된 수열로 만들어야 하는 것이 목표다. 하지만 뒤집기 연산을 "최소한"으로 해서 말이다. 정렬된 수열을 만들기 위해서는 여러 방법이 존재할 수 있지만, 가장 적은 수의 뒤집기 연산을 하기 위해서는 BFS를 통해 입력으로 주어진 수열을 한 번, 두 번, 혹은 ... n번 뒤집어서 나온 각 수열을 "정점"으로 두고, 몇 번 뒤집었느냐를 간선으로 구분 지어주면면 문제를 해결할 수 있을 것 같다. 

 

3 1 2 4 를 생각해보자.

한 번 뒤집은 수열의 후보로 1 3 2 4를 생각해볼 수 있을 것이다. 이를 간선 한 개를 통해 이어진 그래프(바로 인접한 정점)로 보는 것이다. 

 

1 3 2 4 를 한 번 더 뒤집은 수열인 1 2 3 4를 생각해보자.

이미 원래 수열에서 한 번 뒤집은 상태에서, 한 번 더 뒤집었기 때문에, 원래 수열에서는 총 두 개의 간선으로 이어진 정점으로 볼 수 있을 것이다. 

 

정리하자면, 뒤집기의 결과물로 나온 수열을 그래프의 각 "정점"이라고 보는 것이다. 그리고 한 개의 간선으로 이어진(서로 인접한) 정점들은 서로 한 번 뒤집기를 통해 만들 수 있는 수열이다. 

 

이런 식으로 너비 우선 탐색을 하다가, 결과로 나온 수열이 정렬된 수열이라면 몇 번 뒤집었는지 결과를 그대로 출력해주면 된다.

 

하지만 중요한 것은, 이 정점들을 어떻게 표현하지? 였다. 각 정점이 수열을 나타내는 것은 알겠는데, 내가 여태까지 풀어온 그래프 문제는 각 정점이 "정수"를 나타냈기 때문에 꽤 난감했다. 

 

고민을 했지만, 잘 떠오르지 않아 이 부분은 책을 참고했다.

 

아이디어를 보니 내가 너무 어렵게 생각했나 싶었다. 굳이! 정수로 변환할 필요가 전혀 없었다.

그냥 원래 정점을 저장해두던 큐의 자료형을 수열을 담는 벡터로 바꿔주면 됐었다...(너무 틀에 박힌 사고를 했다.. 너무 어렵게 생각하면 안 될 것 같다.)

 

이렇게 해서 구현해본 결과물은 이러하다.

 

예제 출력은 잘 나왔지만, "시간 초과"를 받았다.

void bfs(vector <int> seq){
  map <vector<int>,int> distance;
  queue <vector<int>> que;
  sort(v.begin(),v.end());
  que.push(seq);
  distance[seq] = 0;
  while(!que.empty()){
    auto here = que.front();
    que.pop();

    if(here == v){
      cout << distance[here] << '\n';
      return;
    }
    for(int i = 0; i < N - 1; i++){
      for(int j = i + 2; j <= N ; j++){
        vector <int> temp = here;
        reverse(temp.begin()+i,temp.begin()+j);
        if(distance.count(temp) == 0){
          distance[temp] = distance[here] + 1;
          que.push(temp);
        }
      }
    }
  }
}

 

이제부터라도 시간 복잡도를 계산하는 연습을 좀 해야 겠다. 

8개의 정수로 이루어진 수열의 경우, 8! 개의 경우의 수가 있다. 대충 계산기를 뚜들겨보니, 40320이었다. 근데 테스트 케이스가 1000이니까, 40000000이다. 처음엔 어? 1초에 1억번의 연산을 할 수 있다면, 충분히 통과할 수 있는 코드이지 않나? 생각했었지만, map 자료형에 접근하는 시간을 간과했었다. 진짜 최악의 경우 큐에 상대적으로 마지막에 추가된 정점들, 즉 시작 수열에서 많은 수의 뒤집기 연산을 수행한 정점들은 40000개가 저장된 정점을 매번 탐색하고 비교해야한다. 각 정점에 대해 reverse 연산, 그리고 수열이 map에 있는지 확인하기 위한 count까지 생각하면 시간 초과가 왜 났는지 이해할만 하다. 

 

해결 방법은 "미리 8개의 정수로 이루어진 수열"에 대해 40320개의 정점을 bfs로 생성하고, 각 테스트케이스에 대해 한번만 map에 접근하게 하는 것이다. 추가적으로, 이미 정렬된 수열에서 bfs를 통해 입력으로 주어진 수열을 찾는 것과, 입력으로 주어진 수열에서 정렬된 수열을 찾는 것은 사실 똑같다. 여기서는, 정렬된 수열에서 bfs를 하는 것으로 한다. 내가 생각해본 이유는 이러하다.

 

8개의 정수로 이루어진 수열과 그보다 적은 개수로 이루어진 수열은 비교가 불가능한 것 아니야? 가 질문인 것이다.

예를 들어 1 2 3 4 네 개의 정수로 이루어진 수열을 생각해보자.

여기서는 애초에 뒤에 5 6 7 8 을 건드리지 않는다. 그렇기 때문에 이 네 개의 정수의 어떤 조합이든간에 X X X X 5 6 7 8 이러한 형태의 수열로 귀결된다. 따라서 위에서 "이미 정렬된 수열에서 입력으로 주어진 수열을 찾는 방식"을 택한 것이다. 왜냐하면 1 2 3 4 5 6 7 8에서 

1부터 4까지만 뒤집은 4 3 2 1 5 6 7 8을 찾는 것은 5 에서 8은 건드리지 않고, 1에서 4만 뒤집는 것만으로 구할 수 있기 때문이다. 

 

그래서, N개의 정수로 이루어진 수열(벡터) 뒤에 N+1부터 8까지의 수를 push_back 해준 후에 40320개의 결과 수열이 저장되어있는 map에 접근해서 답을 찾으면 된다. 

 

그리고 주의할 점은 입력으로 주어지는 정수가 항상 1 차이 나게 주어지지 않을 수도 있다는 것이다. 

예를 들어, 길이가 4이면, 4 3 2 1 이 아니라, 40 30 20 10 으로 주어질 수도 있는 것이다. 

그렇기 때문에 이를 8 보다 작거나 같은 수로 변환해줄 필요가 있다.

변환은 쉽다. 각 수에 대해서 전체 수열에서 몇 개의 수보다 큰 지 구하고, 이것으로 바꾸어서 저장해주면 된다.

 

vector <int> newSeq(8);
  for(int i = 0; i < seq.size(); i++){
    int num = 1;
    for(int j = 0 ; j < seq.size(); j++){
      if(seq[i] > seq[j])
        num++;
    }
    newSeq[i] = num;
  }

이런 식으로 말이다.

40 30 20 10이면 40은 30 20 10 보다 크니까 num이 4가 되고, 이를 새 수열로 만들어서 첫 번째 원소에 4로 저장하면 된다!

 

정답 코드

---

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 5e5;

int T, N;
vector <int> v;
map <vector<int>,int> ways;

void bfs(){
  queue <vector<int>> que;
  vector <int> sorted(8);
  for(int i = 0; i < 8; i++)  sorted[i] = i + 1;
  que.push(sorted);
  ways[sorted] = 0;
  while(!que.empty()){
    auto here = que.front();
    que.pop();

    int dist = ways[here];
    for(int i = 0; i < 7; i++){
      for(int j = i + 2; j <= 8 ; j++){
        reverse(here.begin()+i,here.begin()+j);
        if(ways.count(here) == 0){
          ways[here] = dist + 1;
          que.push(here);
        }
        reverse(here.begin()+i,here.begin()+j);
      }
    }
  }
}

void solve(vector<int> seq){
  vector <int> newSeq(8);
  for(int i = 0; i < seq.size(); i++){
    int num = 1;
    for(int j = 0 ; j < seq.size(); j++){
      if(seq[i] > seq[j])
        num++;
    }
    newSeq[i] = num;
  }
  for(int i = seq.size() ; i < 8; i++)  newSeq[i] = i + 1;
  cout << ways[newSeq] << '\n';

}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> T;
  bfs();
  while(T--){
    cin >> N;
    for(int i = 0; i < N; i++){
      int a;
      cin >> a;
      v.push_back(a);
    }
    solve(v);
    v.clear();
  }
	return 0;
}

 

배운 점

---

1. 원하는 형태로 입력을 바꾸어서 저장하는 것. 하나의 배울 점이다.

2. 작은 부분이 전체에 속할 수 있는지 따져보고, 그렇다면, 전체를 모두 구해놓고, 작은 부분이 참고만 하는 식으로 하면 시간을 많이 줄일 수 있다는 것

3. 그래프가 생각보다 다양한 형태로 저장될 수 있다. 꼭 정점이 정수여야만 되는 것은 아니다.