[BOJ 1963] 소수 경로

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

1963번: 소수 경로

 

- 문제 요약

 

첫 번째 줄에 테스트케이스의 수 T가 들어온다.

두 번째 줄부터 T+1번째 줄까지 1000 이상의 네 자리 소수 A와 B가 들어온다.

창영이는 A를 B로 변환하고 싶어 한다.

A를 B로 변경할 때는 조건이 있는데, 한 번에 한 자리의 수만 바꿀 수 있다.

또한 A를 B로 바꾸는 과정에서 A는 계속 소수 상태를 유지해야 한다.

이 조건을 만족하면서 A를 B로 바꾸려 할 때, 변환에 필요한 최소 변경 횟수를 출력하는 프로그램을 작성하시오.

(변환이 불가능한 경우에는 Impossible을 출력한다)

 

 

- 알고리즘 정리

 

에라토스테네스의 체, BFS를 활용하는 문제입니다.

BFS를 돌리면서 입력받는 숫자를 문자열로 처리해 줍니다. ( to_string() 함수 이용 )

그다음, 바꿀 수 있는 모든 자릿수를 바꿔주고 다시 탐색을 시작합니다.

이때, visited[] 배열로 현재 대상으로 하고 있는 소수에 대한 탐색 여부를 확인해줘야 합니다.

이런 식으로 탐색하지 않은 소수들을 큐에 넣어주며 BFS를 돌리면 문제를 해결할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 10001
int t,result,a,b;
bool prime[MAX],visited[MAX],flag;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		flag=false;
	    memset(prime,true,sizeof(prime));
	    memset(visited,false,sizeof(visited));
	    for(int i=2;i<MAX;i++){
	    	for(int j=2;i*j<MAX;j++){
	    		prime[i*j]=false;
			}
		}
		cin>>a>>b;
		queue<pair<int,int> >q;
		q.push({a,0});
		visited[a]=true;
	    while(q.empty()==0){
	    	int cur=q.front().first;
	    	int num=q.front().second;
	    	q.pop();
	    	if(cur==b){
	    		cout<<num<<'\n';
	    		flag=true;
	    		break;
			}
			for(int i=0;i<4;i++){
				int nn;
				for(int j=0;j<10;j++){
					string s=to_string(cur);
					s[i]=j+'0';
					nn=stoi(s);
					if(prime[nn]==false){
						continue;
					}
					if(visited[nn]==true){
						continue;
					}
					if(nn>=MAX-1||nn<1000){
						continue;
					}
					visited[nn]=true;
					q.push({nn,num+1});
				}
			}
		}
		if(!flag){
			cout<<"Impossible"<<'\n';	
		}
	}
}

코드 제출 결과