[1963] 소수 경로

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

1963번: 소수 경로

<문제>

에라토스테네스의 체(전처리) + bfs(최적해 계산)로 접근했다.

이 문제에 적용된 bfs에서 다음 정점은 아래의 조건을 만족해야 한다.

1. 소수
2. 자리수중 한개만 변화
3. 아직 방문하지 않은 상태

이중 소수의 목록을 미리 구함으로서 매 정점마다 (9999-1000+1)개의 수를 탐색하는 것이 아닌,

[1000, 9999]중 소수의 개수만큼만 탐색할 수 있다.

 

(2)의 판별은 아래 소스코드의 check()에서 수행하는데,

cur(현재 정점)과 next(다음 정점)을 받아, 조건 (2)를 만족하면 true를 반환하도록 구현해주었다.

 

(3)은 다른 bfs문제와 다른것이 없다.

현재 정점은 [1000, 9999]사이에 있으므로, 1만개 정도를 선언해주어서 업데이트하면 되겠다.

<소스코드>

#include<bits/stdc++.h>
using namespace std;
bool prime[10003], _visit[10003];
int t, s, e;
vector<int>v;
queue<pair<int,int>>q;
bool check(int cur, int next) {
    int i, a[4] = { 0 }, b[4] = { 0 }, x = cur, y = next;
    for (i = 0; i < 4; i++) {
        a[i] = x % 10;
        x /= 10;
        b[i] = y % 10;
        y /= 10;
    }
    if (a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] != b[3] ||
        a[1] == b[1] && a[2] == b[2] && a[3] == b[3] && a[0] != b[0] ||
        a[0] == b[0] && a[2] == b[2] && a[3] == b[3] && a[1] != b[1] ||
        a[0] == b[0] && a[1] == b[1] && a[3] == b[3] && a[2] != b[2])
        return true;
 
    return false;
}
int main(void) {
    int i, j;
    fill(prime, prime + 10001, true);
    prime[0] = prime[1] = false;
    for (i = 2; i * i <= 10000; i++) {
        if (prime[i] == false)continue;
        for (j = 2 * i; j <= 10000; j += i)
            prime[j] = false;
    }
    for (i = 1000; i <= 9999; i++)
        if (prime[i] == true)v.push_back(i);
    int S = v.size();
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &s, &e);
        while (!q.empty())q.pop();
        q.push({ s,0 });
        memset(_visit, 0, sizeof(_visit));
        _visit[s] = true;
        bool flag = true;
        while (!q.empty()) {
            pair<int,int>cur = q.front();
            q.pop();
            if (cur.first == e) {
                flag = false;
                printf("%d\n", cur.second);
                break;
            }
            for (i = 0; i < S; i++) {
                if (_visit[v[i]] == false && check(v[i], cur.first) == true) {
                    q.push({ v[i],cur.second + 1 });
                    _visit[v[i]] = true;
                }
            }
        }
        if (flag == true)printf("Impossible\n");;
    }
    return 0;
}