1963_소수경로

링크 : https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

접근

시작 숫자 부터 목표 숫자까지 도달하기 위한 거리를 구한다

첫번째~4번째 자릿수를 일일이 변경하며 하나의 숫자로 부터 인접한 숫자를 모두 도출한다

도출 과정 중에 소수가 아닌 수는 인접한 숫자후보에 추가하지 않는다

소수는 에라테노스의 체 알고리즘을 구현하여 판별할 수 있도록 한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <map>

using namespace std;
bool isPrime[10000];

vector<int> newNums(int num, int idx){
    string nstr = to_string(num);
    vector<int> ret, parse;
    parse = vector<int>(4);
    parse[0] = nstr[0] -'0';
    parse[1] = nstr[1] -'0';
    parse[2] = nstr[2] -'0';
    parse[3] = nstr[3] -'0';
    int current = parse[idx];
    
    for(int newNum = 0; newNum < 10 ; newNum++){
        
        if(newNum == current) continue;
        parse[idx] = newNum;
        int number = parse[0]*1000 + parse[1]*100 + parse[2] * 10 + parse[3];
        if(!isPrime[number]) continue;
        ret.push_back(number);
    }
    
    return ret;
}



int main(int argc, const char * argv[]) {
    int t, n, m, here, ans;
    for(int i = 2 ; i < 10000 ; i++){
        isPrime[i] = true;
    }
    for(int i = 2 ; i*i < 10000 ; i++){
        if(isPrime[i]){
            for(int j = i*i; j < 10000 ; j+=i){
                isPrime[j] = false;
            }
        }
    }

    scanf("%d", &t);
    for(int i = 0 ; i < t ; i++){
        scanf("%d %d", &n, &m);
        queue<int>q;
        map<int, int> dist;
        q.push(n);
        dist[n] = 0;
        ans = -1;
        
        
        while(!q.empty()){
            here = q.front();
            q.pop();
            
            if(here == m){
                ans = dist[m];
                break;
            }
            
            for(int i = 0 ; i < 4 ; i++){
                for(int next : newNums(here, i)){
                    //cout<<next<<" ";
                    if(next < 1000) continue;
                    if(dist.count(next) > 0) continue;
                    dist[next] = dist[here] + 1;
                    q.push(next);
                }
                //cout<<endl;
            }
           
        }
        printf("%d\n", ans);
        
    }
    
    return 0;
}