백준 1963 - 소수경로 - bfs,몫 나머지 활용 - C++

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

1963번: 소수 경로

역시 가장 적은 횟수(탐색경로)를 파악하는 문제이기 때문에 bfs를 활용하면 된다.

우선 나는 1000 부터 9999까지의 소수만 담긴 벡터를 만들었다.(isprime,initvector)

그후 bfs를 통해서 가장 최단경로로 탐색할 수 있는 경우의 수를 탐색했다.

물론 bool visited[]를 통해 탐색한 노드는 더 탐색 안하는 식으로,,

 

가장 까다로웠던게 각각 1, 10, 100, 1000의 자리수만 다르고 나머진 다 똑같은 자리수 인지 판단하는 여부였던 것 같다.

성급하게 하려다가 많이 틀려가지고 시간을 좀 잡아먹었는데, 천천히 해결하려고 했다면 좀 더 시간을 절약할 수 있지 않았을 까 싶다.

 

나는 각각 bool을 리턴하는 함수를 만들어서 나는 풀었다.

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
 
using namespace std;
 
int oldpw,newpw;
vector<int> prime;
bool visited[10001];
 
bool exceptonesame(int a, int b){
    if(abs(a-b)<10 && a%100-a%10==b%100-b%10)
        return true;
    return false;
}
bool excepttensame(int a, int b){
    if(a/100==b/100 && abs(a-b)%10 ==0)
        return true;
    return false;
}
bool excepthunsame(int a, int b){
    if(a/1000==b/1000 && abs(a-b)%100 ==0)
        return true;
    return false;
}
bool exceptthosame(int a, int b){
    if(abs(a-b)%1000 ==0)
        return true;
    return false;
}
bool isprime(int n){
    for(int i=2; i<=sqrt(n); i++){
        if(n%i==0)
            return false;
    }
    return true;
}
 
void initvector(){
    for(int i=1000; i<10000; i++){
        if(isprime(i))
            prime.push_back(i);
    }
}
 
int bfs(int oldpw){
    if(oldpw==newpw)
        return 0;
    int answer = 0;
    queue<int> q;
    q.push(oldpw);
    while(!q.empty()){
        int size = q.size();
//        cout<<size<<" "<<answer<<" size is \n";
        for(int i=0; i<size; i++){
            int x = q.front();
            q.pop();
            for(int j=0; j<prime.size(); j++){
                if(visited[prime[j]])
                    continue;
                int dif = abs(prime[j]-x);
                if(exceptthosame(prime[j],x)||excepthunsame(prime[j],x)||excepttensame(prime[j],x)||exceptonesame(prime[j],x)){ //여기서 문제가 있었다. 한자리 수만 바뀌었을때 구현을 제대로 못했음. 한자리 수만 바뀐 상태에서 소수인 것을 어떻게 구현할까? 아이디어가 안떠오르네,
                    if(prime[j]==newpw){
                        return answer+1;
                    }
                    else{
//                        cout<<prime[j]<<" hi \n";
                        visited[prime[j]]=true;
                        q.push(prime[j]);
                    }
                }
            }
        }
        answer++;
//        cout<<"size is "<<q.size()<<"\n";
    }
    return -1;
}
 
int main(void){
    initvector();
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>oldpw>>newpw;
        memset(visited,false, sizeof(visited));
        int result = bfs(oldpw);
        if(result==-1){
            cout<<"Impossible\n";
        } else
            cout<<result<<"\n";
    }
}