[알고리즘 BFS & DFS 8] PRIMEPATH

문제

---

4자리 소수가 2개 주어질때, 시작 수에서 도착 수까지 아래에 주어지는 규칙에 맞게 변경할때 최소 변경 횟수를 구하는 프로그램을 작성해보자. 규칙은 어떤 수에서 다음 수로 넘어갈때 어떤 수의 한 자리수 만 변경해서 이동한다. 각 단계별 수는 소수이다. 만약 1033에서 8179로 가야한다면, 다음과 같은 순서로 이동하게되어 최소 변경 횟수는 6이된다.

copy

1733, 3733, 3739, 3779, 8779, 8179

입력은 항상 네 자리 소수만(1000 이상의 소수) 주어진다고 가정하자. 주어진 두 소수는 ‘네 자리 수’라 하였기 때문에 0013 과 같은 1000 미만의 소수는 입력되지않는다.

 

입력

---

첫 줄에 소수 쌍의 수 T(1 ≤ T ≤ 100)가 주어진다. 다음 T줄에 걸쳐 각 줄에 시작 수, 끝 수에 해당하는 네 자리 소수가 주어진다.

 

출력

---

각 소수 쌍에 대해 두 소수 사이의 최소 변경 횟수를 출력한다. 불가능한 경우 Impossible을 출력한다.

 

예제 입력

3

1033 8179

1373 8017

1033 1033

예제 출력

6

7

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//백준 1963번
 
/*
1. 에라토스테네스의 체로 1~9999까지 소수 판별 함
(arr에 0이 아니고 숫자가 있으면 소수)
 
2. 수 n,m을 입력받고, n 숫자 1000,100,10,1 의 자리를
1씩 더하면서 arr[num]!=0 이고 check[num]==0 이면 방문체크 후 큐에 삽입
 
3. m 숫자를 찾으면 BFS종료 후 cnt 값 출력
 
4. check배열, flag, flag_cnt 초기화 후 위 과정 반복
*/
 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
 
const int MAX = 10005;
const int sPrime = 9999;
 
int arr[MAX];
int check[MAX] ={0,};
 
//에라토스테네스의 체 구현 (1~9999까지 소수 판별)
//arr[i] != 0 이면 소수!
void primeNumber(){
  for(int i=2; i<=sPrime; i++){
    arr[i] = i;
  }
  for(int i=2; i<=sPrime; i++){
    if(arr[i]==0) continue;
    for(int j=i+i; j<=sPrime; j+=i){
      arr[j] = 0;
    }
  }
}
 
//몇번 반복할 것인지..
int endNum;
 
//두 수 입력
int n, m;
 
//숫자를 저장할 큐 생성
queue <pair<int,int>> q;
 
//BFS 도중 수를 찾으면 정지하는 'flag'
//1이면 찾음 0 이면 못찾음.
int flag = 0;
int flag_cnt = 0;
 
//숫자를 각각의 자릿 수로 나누어주는 함수
void BFS(){
  if(q.empty() || flag == 1) return;
  
  int num = q.front().first;
  int cnt = q.front().second;
  q.pop();
  
  //테스트
  //cout<<num<<", "<<cnt<<endl;
  
  if(num == m){
    flag = 1;
    flag_cnt = cnt;
    return;
  }
  
  check[num] = 1;
  
  int a = num/1000;
  int b = (num-a*1000)/100;
  int c = (num-(a*1000)-(b*100))/10;
  int d = (num-a*1000-b*100-c*10);
  //cout<<a<<" "<<b<<" "<<c<<" "<<d;
  
  int sum = 0;
  for(int i=1; i<10; i++){
    sum = i*1000 + b*100+ c*10 +d;
    if(check[sum]==0 && arr[sum]!=0){
      q.push(make_pair(sum, cnt+1));
      check[sum] = 1;
    }
  }
  for(int i=0; i<10; i++){
    sum = a*1000 + i*100 + c*10 + d;
    if(check[sum]==0 && arr[sum]!=0){
      q.push(make_pair(sum, cnt+1));
      check[sum] = 1;
    }
  }
  for(int i=0; i<10; i++){
    sum = a*1000 + b*100 + i*10 + d;
    if(check[sum]==0 && arr[sum]!=0){
       q.push(make_pair(sum, cnt+1));
       check[sum] = 1;
    }
  }
  for(int i=0; i<10; i++){
    sum = a*1000 + b*100 + c*10 + i;
    if(check[sum]==0 && arr[sum]!=0){
      q.push(make_pair(sum, cnt+1));
      check[sum] = 1;
    }
  }
  
  if(!q.empty()) BFS();
}
 
int main(){
  
  primeNumber();
  
  scanf("%d",&endNum);
  
  
  //한개만 테스트
  /*
  cin>>n>>m;
  q.push(make_pair(n,0));
  BFS();
  cout<<flag_cnt<<endl;
  */
  
  for(int i=0; i<endNum; i++){
    scanf("%d %d",&n,&m);
    flag = 0;
    flag_cnt = 0;
    memset(check, 0, sizeof(check));
    while(!q.empty()) q.pop();
    
    q.push(make_pair(n,0));
    BFS();
    
    if(flag == 0){
      cout<<"impossible"<<endl;
    }else{
      cout<<flag_cnt<<endl;
    }
  }
  
  return 0;
}