백준[1963] - 소수 경로

문제

백준 1963 문제 보기

접근 방법

에라토스테네스의 채를 이용해서 1000에서 10000까지의 모든 소수를 구해 놓고 문제를 접근했다. 그 이후 입력된 숫자를 각 자리별로 배열에 담아 bfs로 자릿수를 바꿔 소수인지 아닌지를 판별했다.

코드

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int T, st, fin;
int primeNum[10001];
int v[10001];
int chk[10001];
int num[4];
queue<pair<int, int>> q;
int prime() {
for(int i = 2; i <= 10000; i++){
if(primeNum[i] == false){
if(i > 1000)
v[i] = 1;
for(int j = i + i; j <=10000; j += i){
primeNum[j]=true;
}
}
}
return 0;
}
int main() {
cin >> T;
memset(v, 0, sizeof(v));
memset(primeNum, 0, sizeof(primeNum));
prime();
while(T--) {
memset(chk, 0, sizeof(chk));
bool flag = false;
while(!q.empty()) {
q.pop();
}
cin >> st >> fin;
chk[st] = 1;
q.push({st, 0});
while(!q.empty()) {
int n = q.front().first;
int time = q.front().second;
q.pop();
if (n == fin) {
flag = true;
cout << time << endl;
break;
}
num[0] = n / 1000;
n %= 1000;
num[1] = n / 100;
n %= 100;
num[2] = n / 10;
n %= 10;
num[3] = n;
for(int x = 0; x < 4; x++) {
int temp = num[x];
for (int i = 0; i < 10; i++) {
num[x] = i;
string s = "";
s = (num[0] + '0');
s += (num[1] + '0');
s += (num[2] + '0');
s += (num[3] + '0');
int p = stoi(s);
if (p >= 1000 && p <= 10000 && v[p] && !chk[p]) {
chk[p] = 1;
q.push({p, time + 1});
}
}
num[x] = temp;
}
}
if(!flag) {
cout << "Impossible" << endl;
}
}
return 0;
}
Share