안녕하세요. 문제를 풀다가 막히는게 있어서 글을 씁니다.
Sorting Game ( http://algospot.com/zbxe/?mid=aoj&action=problem&no=169 )
을 푸는 중인데요.
TLE가 나와서 더빠른 솔루션으로 바꿔보려고 해도 잘 떠오르지 않네요.
제가 사용한 방법은 처음 상태(처음에 주어지는 N개의 원소로 이뤄진 수열)에서 k={2~N-1}개를 선택해서 뒤짚을 수 있는 모든 케이스를 BFS로 순회하는 방식으로 사용했습니다. 해는 잘 나오는데 시간이 너무 오래걸리네요.
더 좋은 알고리즘이나 팁 부탁드립니다.
아래는 제가 구현한 소스에서 탐색하는 부분을 알수없는 슈도 코드로 표현했습니다.(?)
~~~ cpp

// N : 주어진 수열의 길이
// q : queue< vector >, 초기상태 q.push( 처음에 주어진 수열 )
// sortedInput : 처음에 주어진 수열을 정렬한 백터
// state : set >, BFS 사이클 방지
while( !q.empty() ){
int qsize = (int)q.size();
for(int cur=0; cur < qsize; ++cur ){ // depth
vector &e = q.front();
if( e == sortedInput ) { // find sol
return result;
}
vector newNum = e;
for(i=0; i < N; ++i){ // 뒤집을 수 있는 모든 경우

for(j=i+1; j < N; ++j){
reverse(newNum.begin()+i, newNum.begin()+j+1);
set::iterator iter = state.find(newNum); // 중복 순회 방지
if( iter == state.end() ){
q.push(newNum);
state.insert(newNum);
}
reverse(newNum.begin()+i, newNum.begin()+j+1);
}
}
q.pop();
}
++result;
}

덧1, 소스코드 하일라이팅은 어떻게 하나요..?
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/qna/58987">원문보기</a>]</div>