백준 1963번 소수 경로 - C++ 풀이

---

 

1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다.
2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다.

 

1. 에라토스테네스의 체를 이용하여 4자리 소수를 모두 구한다.

 네 자리 수가 소수인지 아닌지 판별할 일이 잦으므로 미리 4자리 소수를 모두 구해두어 O(1)에 소수 판별을 할 수 있도록 하자. N 미만의 소수는 에라토스테네스의 체를 사용하면 O(NloglogN)에 구할 수 있다.

 

2. BFS를 이용하여 두 소수 사이의 변환에 필요한 최소 회수를 구한다.

 각 소수를 그래프의 노드라고 생각하면, BFS를 통해 두 소수(노드) 사이의 최단 거리를 구할 수 있다.

 

반응형

---

#include <iostream>
#include <queue>

using namespace std;
const int INF = 987654321;

bool isPrime[10000];

int changeDigit(int n, int base, int to) {
    int ret = n;
    
    ret -= (n / base % 10) * base;
    ret += base * to;
    
    return ret;
}

int BFS(int from, int to) {
    vector<int> visit(10000, INF);
    queue<int> q;
    
    visit[from] = 0;
    q.push(from);
    
    while (!q.empty()) {
        int curr = q.front(); q.pop();
               
        for (int base=1; base<=1000; base*=10) {
            for (int i=0; i<=9; i++) {
                int next = changeDigit(curr, base, i);
                        
                if (next < 1000) continue;
                if (!isPrime[next]) continue;
                if (visit[next] != INF) continue;

                visit[next] = visit[curr] + 1;
                q.push(next);
            }
        }
    }
    
    return visit[to];
}

void calcPrimes() {
    for (int i=2; i<10000; i++) {
        isPrime[i] = true;
    }
    
    for (int i=2; i<10000; i++) {
        if (!isPrime[i]) continue;
        
        int temp = i*2;
        while (temp < 10000) {
            isPrime[temp] = false;
            temp += i;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    calcPrimes();
    
    int T; cin >> T;
    while (T--) {
        int A, B;
        cin >> A >> B;
        
        int ans = BFS(A, B);
        
        if (ans == INF) cout << "Impossible" << "\n";
        else cout << ans << "\n";
    }

    return 0;
}