6. BFS - Sorting Game(sortgame) 문제

문제를 해결하기 위해 배열이 가질 수 있는 각 상태를 정점으로 하는 그래프를 만들고,

해당 그래프에서 입력받은 상태 정점에서 정렬된 상태 정점까지 가는 최소 경로의 길이를 구할 수 있다.

즉, {3,4,1,2} 상태에서 3 4 를 뒤집으면 {4,3,1,2} 가 되므로, 두 정점을 간선으로 연결해주는 것이다.

그러면 bfs를 통해 최소 경로의 길이를 구할 수 있다.

그래프를 만드는 과정은 따로 구현하지 않고, bfs를 할 때 각 정점을 방문할 때마다 해당 정점의 인접한 정점,

즉 해당 상태에서 뒤집어서 만들수 있는 상태들을 계산하여 대기 큐에 넣도록 한다.

// Sorting Game 문제를 해결하는 bfs 알고리즘

int bfs(const vector<int>& perm){

int n = perm.size();

// 입력받은 배열의 정렬된 상태를 미리 계산하여 저장해둔다.

vector<int> sorted = perm;

sort(sorted.begin(), sorted.end());

queue< vector<int> > q;

map<vector<int>, int> distance;  // key값의 상태 정점까지 가는 최소 경로의 길이 = value 값

distance[perm] = 0;

q.push(perm);

while(!q.empty()){

vector<int> here = q.front();

q.pop();

// 현재 방문한 정점이 정렬된 목표 정점이면 종료한다.

if(here == sorted) return distance[here];

// 현재 방문한 정점까지 가는 최소 경로의 길이를 미리 저장해둔다.

int cost = distance[here];

for(int i = 0; i < n; i++){

for(int j = i + 2; j <= n; j++){

// i번째 숫자부터 j번째 숫자까지 배열을 뒤집는다.

reverse(here.begin() + i, here.begin() + j);

// 뒤집은 상태 정점이 아직 발견되지 않았다면(distance에 저장되지 않았다면) 대기 큐에 넣고 거리 계산한다.

if(distance.count(here) == 0){

q.push(here);

distance[here] = cost + 1;

}

reverse(here.begin() + i, here.begin() + j);  // 다시 원상태로 돌려놓는다.

}

}

}

// 오류 있을 경우

return -1;

}

 

위 코드는 문제를 해결할 수 있지만, 그 속도가 너무 느리다.

map에 접근하는데 드는 시간이 크기 때문이다.

따라서 다음 두 가지 속성을 이용하여 위 코드를 최적화 하도록 한다.

1. 배열의 각 숫자들이 값이 다르더라도, 상대적인 크기가 같은 배열들은 최소 경로의 길이가 같다.

예를 들어, {30, 40, 10, 20} 의 결과값은 {3, 4, 1, 2} 와 {45, 78, 22, 24} 의 결과값과 같다.

상대적인 크기를 비교했을때 정렬되어있는 순서가 같기 때문이다.

2. 이 문제에서 사용하는 그래프는 양방향 그래프이기 때문에, 

시작 정점에서 목표 정점까지의 최단 거리는 목표 정점에서 시작 정점까지의 최단 거리와 같다.

그러면 이 두 속성을 이용하여 크기 n의 배열에 대하여 

정렬된 배열 {0, 1, 2, ... , n} 정점에서 다른 모든 상태 정점으로 가는 최소 경로의 길이를 미리 계산해둘 수 있다.

그리고 입력받은 배열을 숫자들의 상대적 크기를 유지하면서 [0, n-1] 범위의 값으로 바꾸면 

이 상태 정점까지가는 최소 경로의 길이를 한번에 구할 수 있다.

map<vector<int>, int> toSort;  // 정렬된 상태에서 다른 모든 상태 정점까지 가는 최소 경로길이를 저장한다.

// 크기 n인 배열에 대하여 정렬된 상태 정점에서 다른 상태 정점까지 가는 최소 경로의 길이를 모두 계산한다.

void preCalc(int n){

vector<int> perm(n);

for(int i = 0; i < n; i++){

perm[i] = i;

}

queue< vector<int> > q;

toSort[perm] = 0;

q.push(perm);

while(!q.empty()){

vector<int> here = q.front();

q.pop();

int cost = toSort[here];

for(int i = 0; i < n; i++){

for(int j = i + 2; j <= n; j++){

reverse(here.begin() + i, here.begin() + j);

if(toSort.count(here) == 0){

toSort[here] = cost + 1;

q.push(here);

}

reverse(here.begin() + i, here.begin() + j);

}

}

}

}

int solve(const vector<int>& perm){

int n = perm.size();

vector<int> fixed(n);

for(int i = 0; i < n; i++){

int smaller = 0;

for(int j = 0; j < n; j++){

if(perm[i] > perm[j]) smaller++;

}

fixed[i] = smaller;

}

return toSort[fixed];

}

위 코드의 경우는 배열의 크기 n에 대해서 각 한번씩만 toSort[]를 계산하면 되므로 이전 코드보다 수십배 시간이 빨라지게 된다.