백준 1963번 - 소수 경로

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

네 자리 수가 있을 때, 숫자를 바꿔가면서 소수를 만들어가는 문제이다.

애초에 1000부터 10000까지 소수인지 아닌지를 구한 뒤에 문제를 풀었다.

그리고 1000의 자리부터 1의 자리까지 숫자를 변경했을 때,

소수이면서 1000보다 작지 않고 이전에 검사한 적이 없으면 큐에 담아서

값이 나올때까지 bfs를 돌리면 된다.

만약 구하려는 값에 가지 못하면 Impossible를 체크해줄 수 있도록 했다.

#include <iostream>
#include <queue>
using namespace std;
 
//n의 i번째 자리 수를 j로 바꾼다 (1234,1,2) -> 2234
int change_prime(int n,int i,int j){
    
    int k=n;
    if(i==1){
        k-=(n/1000)*1000;
        k+=j*1000;
    }else if(i==2){
        k-=((n/100)%10)*100;
        k+=j*100;
    }else if(i==3){
        k-=((n%100)/10)*10;
        k+=j*10;
    }else if(i==4){
        k-=n%10;
        k+=j;
    }
    
    return k;
}
 
int main(){
    
    //소수=1, 소수x=0
    int prime[10000]={0};
    for(int i=1001;i<10000;i++){
        
        prime[i]=1;
        for(int j=2;j<i;j++){
            if(i%j==0){
                prime[i]=0;
                break;
            }
        }
    }
    
    int K;
    cin>>K;
    
    //n1값을 n2값으로 바꿀 때 몇 번(cnt) 바꿔야 하는지
    int n1,n2,cnt;
    for(int testCase=0;testCase<K;testCase++){
        scanf("%d %d",&n1,&n2);
        
        //방문한 적 있는지
        int visited[10000]={0};
        
        queue<pair<int,int>> q;
        visited[n1]++;
        q.push(make_pair(n1,0));
        
        //구하려는 n2 나오는지 유무
        bool check=false;
        
        while(!q.empty()){
            n1=q.front().first;
            cnt=q.front().second;
            q.pop();
            
            if(n1==n2){
                printf("%d\n",cnt);
                check=true;
                break;
            }
            
            int n=0;
            for(int i=1;i<=4;i++){
                for(int j=0;j<=9;j++){
                    n=change_prime(n1,i,j);
                    if(n<1000 || visited[n] || prime[n]==0)
                        continue;
                    
                    visited[n]++;
                    q.push(make_pair(n,cnt+1));
                }
            }
            
        }
        
        if(!check){
            printf("Impossible\n");
        }
    }
 
    return 0;
}