백준[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;
}