[C++] 백준 1327 : 소트 게임

https://www.acmicpc.net/problem/1327

1327번: 소트 게임

 

 

이론적으로 매 번 (N-K) 개의 경우의 수가 있는데

이 경우들 중에 어떤 경우를 선택해야 하냐는 문제

 

우선 그리디로 안되니까 그리디 제외,

규칙성도 찾기 어려우므로 그 외 알고리즘들 몇 개도 제외

브루트 포스로 가야할 것 같은데, (N-K)^(?) 가 되니까 도대체 언제까지 해야될지도 모르겠고

시간복잡도를 생각하기도 어렵다

 

따라서 매 번 N-K의 경우의 수로 바뀐 string이 있을 텐데

해당 string이 나왔었다고 체크해주면 해당 string을 또 봐줄 필요가 없으므로

가지치기도 되고 끝(?)도 있으니까 이런식으로 풀면 된다.

 

여기서 BFS의 "상태" 가 되는 것은 바뀐 string인데,

해당 string의 최대 값(int로 바꾼 후)은 87654321 이므로

bool로 해주면 메모리 안 넘기고 풀 수 있다

bool visit[87654322]//87654321까지 들어가야하니까 87654322

물론 메모리 넘 아까우니까.. (안쓰는 얘들이 넘 많음)

아래처럼 map 써서 해도 된다.

#include <unordered_map>
unordered_map<string, bool> um;//그냥 메모리 아까우니까 bool 쓴거임

아래 코드에서 string을 swap 해주려고 

for (int i = 0; i <= max_idx; i++) {
    string newstring(cur);
    for (int j = 0; j < (K / 2); j++) {
        swap(newstring[i + j], newstring[i + K - 1 - j]);
    }
    ...
}

이런 식으로 조금 복잡하게 썼는데,

algorithm 헤더의 sort나 reverse 사용해주면

for (int i = 0; i <= max_idx; i++) {
    string newstring(cur);
    reverse(newstring.begin() + i, newstring.begin() + i + K);
    ...
}

이렇게 더 깔끔하게 쓸 수 있다

 

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

int N, K;
unordered_map<string, bool> um;
string startstring = "";
string endstring = "";
int max_idx;

int bfs() {
	queue<pair<string, int>> q;
	q.push({startstring, 0});
	um.insert({ startstring, true });

	while (!q.empty()) {
		string cur = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (cur == endstring) {
			return cnt;
		}

		for (int i = 0; i <= max_idx; i++) {
			string newstring(cur);
            //reverse(newstring.begin() + i, newstring.begin() + i + K); 이게 더 나음
			for (int j = 0; j < (K / 2); j++) {
				swap(newstring[i + j], newstring[i + K - 1 - j]);
			}
			if (um.find(newstring) == um.end()) {
				um.insert({newstring, true});
				q.push({ newstring, cnt + 1 });
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d%d", &N, &K);
	max_idx = N - K;
	
	char tmp;
	for (int i = 0; i < N; i++) {
		scanf(" %c", &tmp);
		startstring += tmp;
	}
	
	for (int i = 1; i <= N; i++) {
		endstring += (i + '0');
	}
	printf("%d", bfs());
}