백준 1963 소수 경로

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

 

문제 접근

• 각 케이스를 변경하면서 최소횟수를 구하니까 BFS
  • 각 자리수마다 한자리수만 바꿔서 소수가 될수있는것을 찾아서 큐에 넣어줌
  • 이떄, 중복확인 체크 필요
  • 그럼 소수인지 확인 여부는?, sqrt까지 나머지가 0되는게 있는지여부로 확인

 

시간복잡도 계산

• BFS(V+E)
• V = 총 e4개
• E = 각 숫자에서 각 한자리씩만 바꾸니까 40개씩, e4 * 40= 4e5
  • 그리고 소수인지 각각 체크해야하니까. 4e5 * sqrt(10000) = 4e7

 

인트 계산

• INT 넘어가는수 >> 최소 횟수
• 근데 총 숫자가 e4개 있으니까, 이 횟수는 안넘어갈것임

 

코드

#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
 
bool chk[10010];
bool sosuchk(int esn) {
    for(int i=2; i<= sqrt(esn); i++) {
        if(esn%i==0) return 0;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(chk, chk+10010, 0);
        int num; cin >> num;
        int ans; cin >> ans;
        queue<int> q;
        q.push(num);
        chk[num] = 1;
        
        int cnt=0;
        bool sw = 0;
        
        while(!q.empty()) {
            int qsize = q.size();
            while(qsize--) {
                int eq = q.front(); q.pop();
                if(eq == ans) {
                    sw = 1;
                    cout << cnt << '\n';
                    break;
                }
                
                // 각 자리에서
                for(int k=0; k<4; k++) {
                    // 각 숫자를 대입
                    for(int i=0; i<10; i++) {
                        // 소수이어야하고, 체크에서 이상없어야함
                        if(k==0 && i==0) continue;
                        string es = to_string(eq);
                        es[k] = '0' + i;
                        int esn = stoi(es);
                        if(chk[esn]) continue;
                        if(sosuchk(esn)) {
                            chk[esn] = 1;
                            q.push(esn);
                        }
                    }
                }
            }
            if(sw) break;
            cnt++;
        }
        
        if(sw== 0) cout << "Impossible" << '\n';
        
        
        
    }
    return 0;
}
 

 

문제유형

• BFS - 최소값