BOJ 1963번 소수 경로

BOJ : https://www.acmicpc.net/problem/1963

github : https://github.com/junho0956/Algorithm/blob/master/1963/1963/%EC%86%8C%EC%8A%A4.cpp

 

BFS 로 구현하였습니다.

소수는 아래 코드와 같이 에라토스테네스의 체에 대한 기본개념을 알고 있으면 충분하고

소수를 전부 구해낸 후에,

1자리씩 비교하면서 모든 소수와 비교하여 BFS 로 탐색하였습니다.

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
 
int testcase, N, K;
int sosu[10001];
bool visit[10001];
vector<int> v;
queue<pair<int, int> > q;
 
bool checking(int vnum, int num) {
 
    int cnt = 0;
 
    int check_vnum = vnum;
    int check_num = num;
 
    while (check_num) {
        if (check_num % 10 == check_vnum % 10) cnt++;
        check_num /= 10, check_vnum /= 10;
    }
 
    if (cnt == 3) return true;
    else return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    for (int i = 0; i < 10001; i++) sosu[i] = true;
 
    for (int i = 2; i * i < 10001; i++) {
        if (!sosu[i]) continue;
        for (int k = i * i; k < 10001; k += i) sosu[k] = 0;
    }
 
    for (int i = 1000; i < 10001; i++) if (sosu[i]) v.push_back(i);
 
    cin >> testcase;
    while (testcase--) {
        for (int i = 1000; i < 10001; i++) visit[i] = 0;
        
        cin >> N >> K;
        q.push({ N,0 });
        while (!q.empty()) {
            int now = q.front().first;
            int cnt = q.front().second;
            q.pop();
 
            if (visit[now]) continue;
            visit[now] = 1;
 
            if (now == K) {
                cout << cnt << '\n';
                while (!q.empty()) q.pop();
            }
 
            for (int i = 0; i < v.size(); i++) {
                if (checking(v[i], now)) q.push({ v[i],cnt + 1 });
            }
        }
    }
 
    return 0;
}