[백준] 1963번 : 소수경로 - 에라토스테네스의 체, BFS

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

1963번: 소수 경로

1.문제설명

에라토스테네스 체를 이용하여 미리 소수를 구분할 수 있는 배열을 만들어두고

입력받은 두 소수 A와 B에서

 

A를 시작점으로 하여 자리수를 하나씩 바꿔가면서 소수인지 판별하고 BFS를 돌면서

B로 도착할 수 있는지 확인하는 문제

 

 

 

---

 

다음 숫자를 구하는 식을 꼼꼼하게 잘 세워야 한다.

 

8033

1. 1000의 자리숫자 바꿔가면서 확인

0033 1033 2033 3033 4033 5033 6033 7033 8033 9033

 

2. 100의 자리숫자 바꿔가면서 확인

8033 8133 8233 ... 8933

 

3. 10의 자리 숫자 바꿔가면서 확인

8003 8013 8023 8033 ... 8093

 

4. 1의자리 숫자 바꿔가면서 확인

8030, 8031, 8032, ... 8039

 

 

 

즉 8033이 시작 숫자면

위의 모든 숫자를 한번 씩 보면서

소수인지 확인하고, 1000이상인지 확인하고, 이전에 방문했던 숫자인지 확인하여

BFS를 돌면 된다.

 

 

---

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

bool Prime[10000];


void eratos(){
    fill(Prime, Prime+10000, 1);

    Prime[0] = 0; Prime[1] = 0;
    int sqrtn = int(sqrt(10000));

    for(int i=2; i<=sqrtn; i++){
        for(int j=i*i; j<10000; j+=i){
            Prime[j] = 0;
        }
    }
}


int BFS(int a, int b){
    if(a==b) return 0;

    int vis[10000];
    memset(vis, 0 , sizeof(vis));

    queue<int> Q;
    Q.push(a); vis[a] = 1;


    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(cur==b){
            return vis[cur]-1;
        }

        int minus = 1000;
        for(int i=0; i<4; i++){
            //숫자 계산 확인하기
            int minusedNum = cur - ((cur%(minus*10))/minus)*minus;

            for(int j=0; j<=9; j++){
                int nextNum = minusedNum + j*minus;

                if(Prime[nextNum] && vis[nextNum]==0 && nextNum>=1000){
                    vis[nextNum] = vis[cur] + 1;
                    Q.push(nextNum);
                }
            }
            minus/=10;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;


    eratos();


    for(int T=0;T<t; T++){
        int a, b;
        cin >> a >> b;

        int tmp = BFS(a, b);

        if(tmp<0){
            cout <<"Impossible\n";
        }
        else{
            cout << tmp << '\n';
        }
    }

    return 0;
}

백준 1963번 소수경로