백준 1963번 소수 경로

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

 

 

 

중요한 아이디어는 소수를 구분하는 배열 선언하는 것과, BFS를 한자리씩 바꿔가면서 돌리는 것이다. 뽑아내는것은 바뀐 수에 대한 카운트 값이므로 수를 바꿔 주었으면 전의 카운트 값에서 하나 더해서 queue에 다시 입력 해주고 다음 반복에서 뽑아내는 식으로 한다.

의문점은 visit를 전역으로 선언하고 매 실행시 새로 초기화 하는식으로 하면 물론 되지만 왜 그냥 새로 생성해서 쓰면 안되는지가 의문이다.

->의문 해결 지역은 자동초기화 안됨요 ㅅㄱ

 

 

 

 

 

 

 

 

#include  <iostream> 
#include  <queue>
using namespace std; 


bool prime[10000];

bool visit[10000];


int changed(int n,int i,int j){ 
     
    int k=n; 
    if(i==1){ 
        k-=(n/1000)*1000; 
        k+=j*1000; 
    }else if(i==2){ 
        k-=((n/100)%10)*100; 
        k+=j*100; 
    }else if(i==3){ 
        k-=((n%100)/10)*10; 
        k+=j*10; 
    }else if(i==4){ 
        k-=n%10; 
        k+=j; 
    } 
     
    return k; 
} 



  
int main(void) 
{ 
int K; 

cin >> K; 


for(int i=1001; i<10000; i++) 
{ 
for(int j=2; j<i; j++) 
{ 
if(i%j == 0) 
{ 
prime[i] = true; 
break; 
} 

} 



} 

for(int t=0; t<K; t++) 
{ 
int n1,n2,count; 
bool check = true; 
for(int i=1001; i<10000; i++)

{

visit[i]=false;

}

queue<pair<int,int> > q; 

cin >> n1 >> n2; 

q.push(make_pair(n1,0)); 




while(!q.empty()) 
{ 
n1 = q.front().first; 
count = q.front().second; 
q.pop(); 



if(n1 == n2) 
{ 
   
  cout << count<<endl; 
  check= true; 
  break; 

}






int n = 0; 



for(int i=1; i<=4; i++) 
 for(int j=0; j<=9; j++ ) 
  { 
   
   
   n = changed(n1,i,j); 
   
   if(n>=1000 && !visit[n] && !prime[n]) 
   { 
   
   visit[n]= true; 
   q.push(make_pair(n,count+1)); 
   
   
  } 

   
   
   } 






} 

if(!check) 
{ 

cout<<"Impossible"; 


} 













} 




}