[백준] 소수 경로

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

1963번: 소수 경로

BFS를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

1033 -> 8179 처럼 소수에서 소수로 변환이 일어나야 하는데, 중간에 변경되는 값들은 

1033 1733 3733 3739 3779 8779 8179

처럼 4자리중 1자리 숫자만 달라져야 하고, 각각 또한 소수여야 하고, 1000이상의 4자리 수여야합니다. 

 

이 때, 최소 횟수만에 변환이 일어난다고 하면, 얼마의 변환이 필요한지 출력해야 하고, 만약 불가능하다면, Impossible을 출력해야 합니다.

 

<Solution>

알고리즘은 간단합니다. 

1. queue에 첫번째 숫자를 넣고 방문 표시를 한다. 2. 큐가 빌 때 까지 매번 queue를 pop하고, 한자리 숫자만 바꾼 수에 대해 2-1. 도달해야 하는 수라면 return 2-2. 소수인지 판단하고, 이미 방문했는지 판단하고, 1000보다 작아지지 않는지 판단해서 2-3. 방문표시를 하고 변경한 숫자를 queue에 넣어주어야 한다.

 

이 과정을 실제로 구현하면 아래와 같습니다. 

주의 해야하는 점은, 한자리 숫자를 바꾸는 과정과, 숫자를 바꾸다 1000보다 작아지는 경우 등을 주의해서 생각해서 구현하여야 합니다.

#include <iostream>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
 
int S, E;//출발 정류장 번호, 도착 정류장 번호

void InputData(){
    cin >> S >> E;
}
bool is_prime(int k){
    int min = 2;
    int max = int(sqrt(k)) +1;
 
    if(k == 2) return true;
 
    for(int i = min; i<=max; i++){
        if(k%i == 0) return false;
    }
    return true;
 
}
 
struct k{
    int num, times;
};
 
int solution(){
    char visited[10000];
    memset(visited, 0, sizeof(visited));
    queue <k> my_q;
    k init = {S, 0};
    if(S == E) return 0;
    my_q.push(init);
    visited[init.num] = '1';

    while(!my_q.empty()){
        k e = my_q.front(); my_q.pop();
 
        for(int j = 1; j<=4; j++){
            int p = pow(10,j);
            for(int i = 1; i<=9; i++){
                int new_num=0;
                new_num+=e.num/p * p;
                new_num+=((e.num%p) + i*p/10)% p;
 
                if(new_num < 1000) continue;
 
                if(visited[new_num] == '1') continue;
                if(new_num == E) return e.times+1;
                if(is_prime(new_num)){
                    visited[new_num] = '1';                    
                    my_q.push((k){new_num, e.times+1});
                }
            }
        }
 
    }
    return -1;
}
 
int main(){
    int ans = -1;
    int T;
    cin >> T;
    for(int i = 0; i<T; i++){
        InputData();
 
        ans = solution();
        if(ans == -1) {
            cout << "Impossible" << endl;
        }
        else {
            cout << ans << endl;
        }
    }

    return 0;
}