백준 1963 소수 경로

<링크>

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

<소스코드>

#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
void eratos();
void bfs(int,int);
vector<int> isPrime(10000,1);
int main()
{
    eratos();
    int T,N,K;
    scanf("%d", &T);
    while (T--) 
    {
        scanf("%d%d", &N, &K);
        bfs(N,K);
    }
}
void bfs(int S,int D)
{
    queue<int> q;
    vector<int> isVisited(10000, 0);
    q.push(S);
    int depth = 0;
    while (!q.empty())
    {
        int s = q.size();
        for (int i = 0; i < s; ++i)
        {
            int c = q.front();
            q.pop();
            if (c == D) {
                printf("%d\n", depth); return;
            }
            string num = to_string(c);
            for (int j = 0; j < 4; ++j)
            {
                string tmp = string(num);
                for (int k = '0'; k <= '9'; ++k)
                {
                    tmp[j] = k;
                    int to = stoi(tmp);
                    if (isPrime[to] && !isVisited[to] && to >= 1000)
                    {
                        isVisited[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        ++depth;
    }
    printf("Impossible\n"); 
    return;
}
void eratos()
{
    for (int i = 2; i <= 100; ++i)
    {
        if(isPrime[i])
        for (int j = i * 2; j <= 9999; j += i)
        {
            isPrime[j] = 0;
        }
    }
}

<풀이>

각 자리마다 번호를 0~9까지 바꿔가면서 탐색한다.

소수이면서 && 방문 안했고 && 1000이상일때만 큐에 넣는다.

한 자리만 번호를 바꿔야하므로 구현하기 귀찮아서 string을 이용했다.

소수인지 판가름하기도 좀더 빠르게 하려고 에라토스테네스의 체를 이용했다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 그냥다 소수라고 가정하고 배열 만듬 (전부 소수라고 체크)

2. 2부터 루트N까지 소수라고 체크되어있으면 배수는 다 제거