백준 - 1963 소수경로

문제 링크

문제에서 풀이 방법을 가르쳐주었기 때문에 그냥 그 로직대로 따라가 풀었다. 코드 라인이 쓸대없이 길어져서 귀찮았던 것 같다.

나는 에라스토테네스의 체로 소수들을 전부 구하고 시작했는데, 풀고 보니 에라스토테네스의 체같은건 필요 없고, 그냥 평범하게 소수를 구하거나 그때그때 판별해도 상관없는 문제였다...

어쨌든 각 각 자리수를 바꿀수 있는 한도 내에서 바꾼 뒤, 해당 숫자의 이전 방문 여부와 에라스토테네스의 체로 구한 배열에서 소수인지 판별하고 큐에 넣어서 반복해주었다.

처음엔 그냥 숫자로만 풀이하려다가 숫자를 배열로, 배열을 숫자로 바꿔서 풀이하였다. 근데 바꾸나 마나였단 생각이 든다...

밑에는 풀이 코드이다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue> 
using namespace std;
int t, x, y, a[10000] = { 0, }, visited[10000] = { 0, }, num[4];
typedef struct {
    int num, count;
}Prime;
queue<Prime> q;
//에라토스테네스의 체로 9999이하의 소수들을 모두 구한다. 
void era(int n) {
    int i;
    while (true) {
        for (i = 2; i <= n; i++)
            if (a[i] == 0) break;
        if (i>n) return;
        a[i] = 1;
        for (int j = 2; j*i <= n; j++) {
            if (a[i*j] == 0) {
                a[i*j] = 2;
            }
        }
    }
}
//배열을 숫자로 바꾼다.
int numToArr(){
    int ret=0;
    for(int i=0; i<4;i++){
        ret+=num[i]*pow(10,3-i);
    }
    return ret;
}
//자리수를 한번 바꾼 값이 소수인지 판별하고, 소수이면 큐에 넣는다.
void check(int i,int count){
    int k = i==0?0:1;
    int bak = num[i];
    while(num[i]-1>=1-k){
        num[i] -=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
    while(num[i]+1<=9){
        num[i] +=1;
        int n = numToArr();
        if(a[n]==1&&visited[n]==0){
            Prime p1 = {n,count+1};
            visited[n]=1;
            q.push(p1);
        }
    }
    num[i]=bak;
}
//너비우선 탐색.
int dfs() {
    Prime p = { x,0 };
    q.push(p);
    while (!q.empty()) {
        p = q.front(); q.pop();
        //값을 찾았으면 카운트값을 반환 
        if (p.num == y) return p.count;
        //숫자를 배열로 변경 
        for(int i=0;i<4;i++){
            num[i] = p.num/pow(10,3-i);
            p.num = p.num-num[i]*pow(10,3-i);
        }
        for(int i=0;i<4;i++){
            check(i,p.count);
        }
    }
    //못찾았으면 -1을 반환한다. 
    return -1;
}
int main() {
    era(9999);
    scanf("%d",&t);
    while(t--){
        scanf("%d %d", &x, &y);
        int ret = dfs();
        printf(ret==-1?"Impossible\n":"%d\n",ret);
        while(!q.empty())q.pop();
        memset(visited,0,sizeof(visited));
    }
}