[백준][1963번][BFS] 소수경로

소수 경로

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

<코드>

#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
int primGroup[10001];
 
struct couple{
    int a;
    int b;
};
 
couple make_couple(int a, int b){
    couple temp;
    temp.a = a;
    temp.b = b;
    return temp;
}
 
int main(void){
 
    int a[10001] = {};
    int primGroup[10001] = {};
    vector<int> prim;
 
    for (int i = 2; i <= 10000; i++)
    { 
        if (a[i] == 0)
        {
            int count = 1;
            prim.push_back(i);
            a[i*count] = 1;
            while (i*count <= 10000){
                a[i*count++] = 1;
            }
 
        }
        else
            continue;
    }
 
    for (int i = 0; i < prim.size(); i++)
        primGroup[prim[i]] = 1;
 
    int testcase;
    scanf("%d", &testcase);
    
    while (testcase--){
        int first, end;
        int result = -1;
        int visit[10001] = {};
        queue<couple> que;        // 처음은 int 는 숫자 다음 int는 count;
        scanf("%d %d", &first, &end);
 
        que.push(make_couple(first,0));
        visit[first] = 1;
        pair<int, int> a;
        while (!que.empty()){
            couple temp = que.front();
 
            int Digit[4];
            int tempNum = temp.a;
            int d[4] = { 1000, 100, 10, 1 };
 
            if (temp.a == end){
                result = temp.b;
                break;
            }
 
            for (int i = 0; i < 4; i++){
                Digit[i] = tempNum / d[i];
                tempNum = tempNum%d[i];
            }
 
            que.pop();
 
            for (int i = 0; i < 4; i++){
                tempNum = temp.a - Digit[i] * d[i];
                for (int j = 0; j <= 9; j++)
                {
                    int compareNum = tempNum + d[i] * j;
                    if (i == 0 && j == 0)
                        continue;
 
                    if (primGroup[compareNum] == 1 && visit[compareNum] == 0){
                        visit[compareNum] = 1;
                        que.push(make_couple(compareNum, temp.b + 1));
                    }
 
                }
            }
 
        }
        if (result == -1)
            printf("Impossible\n");
        else
            printf("%d\n", result);
    }
    return 0;
}

<문제 푼 요령>

 1. 먼저 에라토스 체를 이용하여서 소수만 구하게 된다.

 2.구한 소수들을 primGroup으로 따로 체크를 해서 나중에 index만으로 소수인지 아닌지를 바로 알 수 있게 만들어 놨다.

 3. 처음 네 자리 수에서 두번째 네 자리 수를 바꾸는 과정을 거칠때도 그 숫자들은 소수여야하는 전재 조건이 매우 중요하다.

 4. 처음 수에서 각자리수별로 바꿔가면서 새로운 숫자를 만들어보는데 여기서 이 새로운 숫자가 소수인지 판별을 하고 이전에 이 숫자가 나왔는지 판별하여서 새롭게 나온 숫자로 부합하면 큐에 이 숫자를 집어넣는다.

 5. 이렇게 큐에 집어넣고 빼고를 반복하는 BFS 탐색 방법을 이용하여 보면 두 소수를 변환에 필요한 최소 회수를 출력할 수 있고 만약 불가능한 경우는 result가 한번도 갱신이 되지 않기 때문에 판별할 수 있다.