[BOJ/백준][Gold4] 1963 : 소수 경로 (C++)

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

1963번: 소수 경로

 

 

[난이도] Gold4
[유형] BFS

[풀이]
1~9999의 숫자중에 소수를 미리 구해 놓은 뒤.
visit[10000] 와 같은 배열을 선언해서
처음 주어진 숫자부터 한 자리씩 바꿔가며 BFS를 진행하면 된다.

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int T,a,b;
bool visit[10000],prime[10000];
int main(){
    
    prime[1]=1;
    for(int i=2;i<10000;i++){
        if(prime[i]) continue;
        for(int j=i*2;j<10000;j+=i) prime[j]=1;
    }
    scanf("%d",&T);
    while(T--){
        
        scanf("%d%d",&a,&b);
        memset(visit,0,sizeof(visit));
 
        queue<int> q;
        q.push(a);
        visit[a]=1;
        int cnt=0;
        bool ok=0;
        while(!q.empty()){
 
            int sz=q.size();
            while(sz--){
 
                int qf = q.front(); q.pop();
                if(qf==b){
                    printf("%d\n",cnt);
                    ok=1;
                    break;
                }
                string cur = to_string(qf);
                for(int i=0;i<cur.size();i++){
                    for(int j=0;j<10;j++){
                        if((i==0&&j==0) || (cur[i]-'0')==j) continue;
                        string nxt = cur;
                        nxt[i]=j+'0';
                        int ni= stoi(nxt);
                        if(prime[ni] || visit[ni]) continue;
                        visit[ni]=1;
                        q.push(ni);
                    }
                }
            }
            if(ok) break;
            cnt++;
        }
        if(!ok) puts("Impossible");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1963.cpp