BFS 암걸리는 문제
함정이 많이 존재한다.
1. 연산을 K번할 수 없을 경우
한 자리수는 연산할 수 없다.
또 두 자리수중 10의 배수또한 연산할 수 없다.
(나는 처음에 2000 이나 50000같이 가장높은 자리수의 값만 존재하는 수도 안되는 줄알았다.
0 → 0 이동 가능)
2. 바꾼수가 0으로 시작하면 안됨
이건 Pass
3. 방문한 곳 탐색
방문한 곳을 다시 탐색하면 메모리 초과가 발생한다.
하지만 보통의 방문탐색방법을 사용한다면
N=7522,K=3 에서와 같은 예에서 7522가 나오지 않을 것이다.
따라서 방문배열을 다시 초기화시켜준다.
나는 안전하게 앞으로 더 탐색해야할 개수를 P라하면
P가 짝수일때 최댓값을 갱신해주었다.
(사실 위의 과정을 처리했으면 필요없음)
#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int ans = 0;
queue<int> q;
int size(int N){
for (int m = 7, n = 1000000; n >= 1; n /= 10, m--)
if (N / n > 0) return m;
return 1;
}
int main(){
int N, M, K;
scanf("%d%d", &N, &K);
M = size(N);
if (M == 1 || (M == 2 && N % 10 == 0)){ //일의자리, 십의자리인 10의 배수 - false
printf("-1\n");
return 0;
}
q.push(N);
int cnt = 0;
for (int cnt = 0; cnt <= K; cnt++){
int sz = q.size();
bool visit[1000001] = { 0 };
for (int s = 0; s < sz; s++){
int num = q.front();
q.pop();
if (cnt == K || ((K - cnt) & 1) == 0){ //K에 도달, 짝수만큼 남았을 때
ans = ans < num ? num : ans;
if (cnt == K) continue;
}
string str = to_string(num);
for (int n = 0; n < M - 1; n++){
for (int m = n + 1; m < M; m++){
if (n == 0 && str[m] == '0') continue;
int s2i;
char tmp = str[n];
string nstr(str);
nstr[n] = nstr[m];
nstr[m] = tmp;
s2i = stoi(nstr);
if (!visit[s2i]){
q.push(s2i);
visit[s2i] = true;
}
}
}
}
}
printf("%d\n", ans);
return 0;
}
| cs |
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int N, K;
int len;
bool visit[1000001];
int getlen(int x) {
string s = to_string(x);
return s.length();
}
int bfs() {
int cnt = 0;
int ans = -1;
queue<int> q;
q.push(N);
visit[N] = true;
while (!q.empty()) {
int size = q.size();
memset(visit, 0, sizeof visit);
++cnt;
for (int s = 0;s < size;s++) {
int here = q.front();
string str = to_string(here);
q.pop();
for (int n = 0;n < len;n++) {
for (int m = n + 1;m < len;m++) {
string tmp = str;
if (n == 0 && str[m] == '0') continue;
swap(tmp[n], tmp[m]);
int get = stoi(tmp);
if (!visit[get]) {
visit[get] = true;
q.push(get);
if (cnt == K) ans = max(ans, get);
}
}
}
}
if (cnt == K) break;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> K;
len = getlen(N);
cout << bfs();
return 0;
}
| cs |
댓글 없음:
댓글 쓰기