[백준] 1963번 - 소수 경로 (C++) 문제 및 풀이

문제) 백준 - BFS - 소수 경로

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

1963번: 소수 경로

 

주어진 첫 소수의 한 자리를 바꾸어 두 번째 소수를 만들 수 있는 최소 변환 수를 구하는 문제였습니다. 에라토스테네스의 체를 활용하여 10000 이하에 대하여 소수 판별(isPrime)을 진행합니다. 그 후 주어진 수의 첫자리부터 4번째 자리까지 변환하면서 소수이면서 방문하지 않은 수에 대하여 queue에 push 하여 BFS를 진행합니다.

 

C++ 소스 코드)

	bool isPrime[MAX];
	int dist[MAX];
	void makePrime(){
	isPrime[0] = false;
	isPrime[1] = false;
	for(int i = 2; i <= int(sqrt(MAX)); ++i){
	if(isPrime[i])
	for(int j = i * i; j < MAX; j += i)
	isPrime[j] = false;
	}
	}
	int bfs(int a, int b){
	memset(dist, -1, sizeof(dist));
	queue<int> q;
	q.push(a);
	dist[a] = 0;
	while(!q.empty()){
	int now = q.front();
	q.pop();
	if(now == b) return dist[b];
	// a를 한자리씩 바꿈 1234
	// vc 1 2 3 4
	int temp = now;
	vector<int> vc;
	for(int i = 0; i < 4; ++i){
	vc.push_back(temp % 10);
	temp /= 10;
	}
	reverse(vc.begin(), vc.end());
	for(int i = 0; i < 4; ++i){
	for(int pos = 0; pos <= 9; ++pos){
	if(pos == vc[i]) continue;
	int next = 0;
	for(int j = 0; j < 4; ++j){
	if(i == j)
	next += pow(10, 3 - j) * pos;
	else
	next += pow(10, 3 - j) * vc[j];
	}
	if( next < 10000 && next >= 1000 && dist[next] == -1 && isPrime[next]){
	dist[next] = dist[now] + 1;
	q.push(next);
	}
	}
	}
	}
	return -1;
	}

view raw 1963.cpp hosted with ❤ by GitHub

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/1963_%EC%86%8C%EC%88%98%EA%B2%BD%EB%A1%9C.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions