(출처) https://algospot.com/judge/problem/read/SORTGAME
입력으로 들어오는 n이 굉장히 작다
해당 문제는 최대로 들어올 수 있는 n은 8로 굉장히 작다. 이 작은 입력값을 보고 뭔가 완전탐색같은 느낌으로 해결하면 되지 않을까라는 느낌이 들었다.
그래서 주어진 수열을 하나의 정점으로 보고 해당 수열로 뒤집어서 만들 수 있는 다른 수열들과 간선을 연결하는 방식으로 문제를 해결하면 되지 않을까라는 생각이 들었다.
수열의 최대 길이가 8이므로 존재하는 정점 개수의 최대는 8!이고, 각각의 정점 당 뒤집을 수 있는 방법이 23개가 존재한다.
따라서 각 정점마다 23개의 간선을 갖는 약 4만 개의 정점의 그래프를 탐색하는 문제라고 생각하면 충분히 2초라는 시간 안에 문제를 해결할 수 있다고 보았다.
수열들로 어떻게 그래프로 만들지?
문제는 하나의 수열을 어떻게 정점으로 표현해야 할지 감이 잘 오지 않았다. 특정수열을 인자로 넣어주면 해당 수열과 일대일 대응하는 정수 인덱스를 리턴해주는 함수를 작성하고 싶었지만 제대로 아이디어가 떠오르지 않았다.
수열에 원소들의 모임을 전부 모아 하나의 비트로 표현해 나타내볼까도 싶었지만 해당 방법으로는 특정 정점을 특정 정수로 알맞게 일대일 변환 시킬 수는 있어도, 모든 정점들이 결국 규칙성이 없는 여러 정수값으로 발산하고 있는 형태를 이루고 있을 텐데, 이 규칙성이 없는 정수값들을 어떻게 규칙적인 형태로 나타내어 인덱싱을 지어주어야 할지 감이 잡히지 않았다.
고민을 하다가 그냥 책을 보았더니, 책에서는 그래프를 미리 만들어놓고 탐색을 진행하는 것이 아니라 탐색을 진행하면서 다음으로 방문해야 할 정점을 즉각적으로 생성하며 문제를 해결하는 것을 볼 수 있었다.
또한 수열을 표현하는 벡터 배열을 통째로 map의 키로 집어넣어서 굳이 정점들의 인덱싱 처리를 고려하지 않고 각 정점들의 시작정점과의 거리를 곧바로 계산하더라.
확실히 문제에서 요하는 정답은 입력으로 주어진 시작점 수열에서부터 정렬된 수열로 이어지는 경로의 최솟값, 즉 최단거리 값이므로 굳이 그래프를 전부 만들어 놓고서 탐색을 진행할 필요도 없었고, 애당초 수열이라는 특정 상태들끼리의 간선 연결을 이차원 배열로 표현하여 그래프를 만들려고 했던 것 자체가 굉장히 이상했던 것 같다.
결국 해당 문제는 굳이 그래프를 미리 만들 필요 없이, 시작 정점에서부터 map 자료형에 상태 자체(수열)를 key로 담아놓고 해당 상태와 이어지는 다음 상태로 탐색을 진행하면서 시작점으로부터 떨어진 거리가 얼마나 되는지만을 기록하면서 문제를 해결한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
queue<vector<int>> q;
map<vector<int>, int> distance_map;
vector<int> flip(vector<int> &here, int box, int index) {
int n = box / 2;
vector<int> ret = here;
int start_i = index;
int last_i = start_i + box;
reverse(ret.begin() + start_i, ret.begin() + last_i);
return ret;
}
void conversing(vector<int>& inputs) {
vector<int> sorted_inputs = inputs;
sort(sorted_inputs.begin(), sorted_inputs.end());
for (int i = 0; i < inputs.size(); i++) {
for (int j = 0; j < sorted_inputs.size(); j++) {
if (inputs[i] == sorted_inputs[j]) {
inputs[i] = j + 1;
break;
}
}
}
}
void sortgame_bfs(vector<int>& here) {
distance_map[here] = 0;
q.push(here);
int n = here.size();
//O(N!)
while (!q.empty()) {
here = q.front();
q.pop();
for (int box = 2; box < n + 1; box++) {
for (int index = 0; index < n - box + 1; index++) {
vector<int> there = flip(here, box, index);
//O(logN)
if (distance_map.count(there) == 0) {
q.push(there);
distance_map[there] = distance_map[here] + 1;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int sizemap = 0;
vector<int> here;
here.reserve(10);
for (int i = 3; i < 10; i++) {
here.clear();
for (int j = 1; j < i; j++) {
here.push_back(j);
}
sortgame_bfs(here);
}
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<int> inputs;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
inputs.push_back(temp);
}
conversing(inputs);
cout << distance_map[inputs] << "\n";
}
return 0;
}기억하고 싶은 점
그래프를 어느 수준까지 구현해야 하는지, 어떤 자료구조를 이용해서 표현할 것인지, 그래프 탐색은 어느 수준까지 필요한 것인지, 모든 정점을 전부 방문하면서 특정 자료를 얻어내야 하는 것인지, 아니면 어떤 두 정점을 잇는 간선만을 따라가야 하는 것인지 등등 그래프 문제를 풀 때는 위와 같은 내용들을 미리 생각해 전체 과정을 얼추 머리속에 그려놓고 해결해야겠다는 느낌을 받았다.
또한 수열(상태)을 인덱싱하기위해 map의 key로 벡터 그 자체를 넣어주어 사용하는 것은, 벡터 크기 비교 연산에 얼마만큼의 계산소모가 필요한 지 잘 모르겠어서 시간적인 측면의 효율은 모르겠지만 적어도 메모리 측면에서 굉장한 비효율적인 것은 뻔히 눈에 보인다.
한 번 찾아보니 내가 처음 생각했던 것처럼 비트마스크를 이용해서 정수로 변환이 가능하다고 하던데 나중에 한번 시도해봐야겠다.
