1963 - 소수 경로

에라토스테네스의 체로 소수를 걸러내면서 4자리의 소수 1001 ~ 9973를 모두 저장했다.

소수 X 에서 1자리의 변화로 가능한 수를 "인접리스트"처럼 만들었다.
예를 들면, 1021에서 이동 가능한 다음 소수는 1031, 1051, 1061, 1091, 1321, 1621, 1721, 4021, 5021 이다.

이게 가능한 이유는

1. 소수에서 출발하여 소수로 끝난다.
2. 중간 과정에서도 항상 4자리 소수임이 유지된다.

이기 때문이다.

그리고 이렇게 만들어진 인접리스트로 BFS를 돌렸다.

처음에는 "특정 소수 S 에서 다음 소수 T 까지의 최소 거리"를 누적하면서 DP를 하려 했다.

vector<int> adj[9999]; /* 이 소수로부터 1의 변화로 갈 수 있는 인접 소수 */
 
int S, T; /* S에서 T로 만들어야 함 */
int dp[9999]; /* memset(-1, .. */
 
int f(int cur){
    if(cur == T) return 0;
     
    int& r = dp[cur];
    if(r != -1) return r;
    r = INF;
    for(int i=0; i < adj[cur].size(); ++i){
        r = min(r, 1+f(adj[cur][i]));
    }
    return r;
}

왜냐하면 시작 소수를 S, 목적지를 T, 중간에 거친 임의의 소수를 K 라고 하면 K->T의 최소와 S->K 의 최소가 곧 S->T 가 되는 최소 거리라고 생각했기 때문이다.

안되는 이유를 못 찾아서 결국 BFS로 했는데, 8179 1733 와 1733 8179 의 케이스에서 서로 다르게 나오는 데, 나중에 자세히 디버깅해봐야겠다.

참고로 시작점이 소수인 이상, 문제에서 말하는 불가능한 경우는 존재하지 않는다.

BFS로 해결하는 소스는 아래와 같다.



크게 다른게 없다.

scanf("%d %d", &S, &T);
         
int minCost[9999]={};
for(i=999; i<10000; ++i) minCost[i]=INF;
 
queue<pii> q;
q.push({S, 0});
minCost[S] = 0;
while(!q.empty()){
    pii cur = q.front();
    q.pop();
    int curPrime = cur.first, curLen = cur.second;
    for(i=0; i<adj[curPrime].size(); ++i){
        int nextPrime = adj[curPrime][i];
        if(curLen+1 <= minCost[nextPrime]){
            minCost[nextPrime] = curLen+1;
            q.push({nextPrime, curLen+1});
        }
    }
}
printf("%d\n", minCost[T]);