(C++) - 백준(BOJ) 1963번 : 소수경로

www.acmicpc.net/problem/1963

1963번: 소수 경로

bfs로 푼 문제였습니다.

 

 

풀이방법

 1. 에라토스테네스의 체를 이용해 9999까지의 소수를 모두 구합니다. primt[index]이 0이라면 index는 소수입니다.

 2. bfs 시행 : 체크가 안되어 있고 소수인 모든 수를 queue에 push합니다. push할 때는 원래 소수경로의 거리 + 1을 다음 수의 check배열에 저장해줍니다. string으로 수를 변환하면 코드를 더 깔끔하게 할 수 있습니다. 이 후 한 번씩 pop하면서 b와 같은지 비교합니다. pop했을 때 값이 b와 같으면 바로 return 해줍니다. 처음 check시 1로 저장했으므로 return 할 때는 -1한 값을 반환합니다. 모든 수를 확인했을 때 답이 없다면 최대값 0x3f3f3f3f(약 10억)을 반환합니다.

 3. 답 출력 : 최대값이 나왔다면 Impossible을, 아니라면 수를 출력합니다.

Code

#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f
using namespace std;
int t, prime[10000], ck[10000];

void makePrime(){
    for(int i = 2; i*i <= 9999; i++){
        if(!prime[i])
            for(int j = i+i; j <= 9999; j+=i) 
                prime[j] = 1;
    }
}

int bfs(string a, string b){
    queue <string> q;
    q.push(a);
    ck[stoi(a)] = 1;
    while(!q.empty()){
        string x = q.front();
        q.pop();
        if(x == b) return ck[stoi(b)] - 1;

        for(int j = 0; j < 4; j++){
            string tmp = x;
            for(int i = 0; i < 10; i++){
                if(!i && !j) continue;
                tmp[j] = i + '0';
                int newX = stoi(tmp);
                if(!ck[newX] &&!prime[newX]){
                    ck[newX] = ck[stoi(x)] + 1;
                    q.push(tmp);
                }
            }
        }
    }
    return MAX;
}

int main(){
    cin >> t;
    makePrime();
    while(t--){
        string a, b;
        memset(ck,0,sizeof(ck));
        cin >> a >> b;
        int ans = bfs(a,b);
        if(ans!=MAX) cout << ans <<'\n';
        else cout << "Impossible\n";
    }
}