[BOJ] ReverseSort - Compy's Blog

ReverseSort

TimeLimit	MemoryLimit	Condition	TAG
5s	512MB	(1 ≤ N ≤ 10)	BFS, Meet In The Middle

문제가 조금 많이 당황스러웠습니다. 처음에 N이 10 이하인데 이렇게 시간을 많이 준다고? 뭐지? 하면서 생각을 해보니 생각보다 전체 순회는 안되고, 따로 최적해를 구하는 로직이 필요한데 쪼갠다는 생각을 하고서 어떻게 구현해야되는 것인지를 생각하는게 오래걸렸네요.

MITM을 풀어본적이 ctf 때나 있었던 거 같은데 ps에서 보니 반갑기도 하면서 아이디어 떠오르는게 왜 오래걸린지 잘 이해가 되지 않았던 문제였습니다.

구현은 단순히 입력으로 들어온 상태와 완성된 상태에서 이어질 수 있는 경우들을 reverse 시키면서 그 상태를 저장시키고(path로 저장), 만약 그 key에 도달하면 forward list와 backward list의 key 겹치는 개수를 더해서 정답을 출력하도록 만들었습니다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
using namespace std;
int N;
struct Node {
    vector<int> arr;
    vector<pair<int,int>> ops;
};

string encode(const vector<int>& arr) {
    string s;
    for (int x : arr) s.push_back(char(x));
    return s;
}

template <typename T>
void listReverse(vector<T>& list, int left, int right){
    while(left < right){
        T tmp = list[left];
        list[left] = list[right];
        list[right] = tmp;
           
        left++;
        right --;
    }
}

string solution(queue<vector<int>>& q,
                unordered_map<string, vector<pair<int,int>>>& vis,
                unordered_map<string, vector<pair<int,int>>>& other,
                bool forward){
  int sz = q.size();
  while (sz--) {
      auto cur = q.front(); q.pop();
      string ck = encode(cur);
      auto ops = vis[ck];

      int n = cur.size();
      for (int i = 0; i < n; i++) {
          for (int j = i+1; j < n; j++) {
              auto nxt = cur;
              listReverse(nxt, i, j);

              string nk = encode(nxt);
              if (!vis.count(nk)) {
                  auto newOps = ops;
                  newOps.push_back({i, j});
                  vis[nk] = newOps;
                  q.push(nxt);

                  if (other.count(nk)) {
                      return nk;
                  }
              }
          }
      }
  }
  return "";
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    
    cin >> N;
    vector<int> start(N);
    vector<int> goal(N);
    for (int i = 0; i < N; i++){
        cin >> start[i];
        goal[i] = i + 1;
    }

    if (start == goal) {
        cout << 0 << "\n";
        return 0;
    }

    unordered_map<string, vector<pair<int,int>>> fwd, bwd;
    queue<vector<int>> qf, qb;

    fwd[encode(start)] = {};
    bwd[encode(goal)] = {};
    qf.push(start);
    qb.push(goal);

    string meetKey;

    while (!qf.empty() && !qb.empty()) {
        // 앞쪽
        meetKey = solution(qf, fwd, bwd, true);
        if (!meetKey.empty()) break;

        // 뒤쪽
        meetKey = solution(qb, bwd, fwd, false);
        if (!meetKey.empty()) break;
    }

    
    auto ops1 = fwd[meetKey];
    auto ops2 = bwd[meetKey];
    

    cout << ops1.size() + ops2.size() << "\n";

}