(c++)백준 1963번: 소수 경로

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

1963번: 소수 경로

[풀이]

소수는 에라토스테네스의 체 알고리즘을 이용하여 구하였다.

에라토스테네스의 체 알고리즘은 2부터 구하고자 하는 범위의 수들을 배열에 넣어 소수가 아닌 수를 체크하는 알고리즘이다.

2를 제외한 2로 나누어 떨어지는 값 체크 → 3을 제외한 3으로 나누어 떨어지는 값 체크 → (4는 이미 체크 되었으므로 패스) → 5를 제외한 5로 나누어 떨어지는 값 체크 → ··· 마지막까지 체크되지 않은 값들이 소수이다.

bfs를 이용하여 네자리수를 한 자리씩 바꿔가며 소수면 queue에 저장하고 check배열에 수를 몇번 바꿨는지 저장해준다.

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

int T;
bool Prime[10000];
int check[10000];

//에라토스테네스의 체
void findPrime() {
	//i의 배수인 수 모두 false처리
	for (int i = 2; i*i <= 9999; i++) {
		if (Prime[i] == false)continue;
		for (int j = i * i; j <= 9999; j += i) {
			Prime[j] = false;
		}
	}
}

void bfs(int start, int dest) {
	queue<int>q;
	q.push({ start });
	check[start] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (x == dest)return;
		//맨 앞부터 4자리 검사
		for (int i = 0; i < 4; i++) {
			//한 자리씩 확인할 때마다 원래 수로 돌아감
			int sep[4] = { (x / 1000),(x % 1000) / 100,(x % 100) / 10,(x % 10) };
			//0부터 9로 바꿔보기
			for (int j = 0; j <= 9; j++) {
				if (sep[i] == j)continue;
				sep[i] = j;
				int realNum = sep[0] * 1000 + sep[1] * 100 + sep[2] * 10 + sep[3];
				if (realNum > 1000 && Prime[realNum] == true && check[realNum] == -1) {
					check[realNum] = check[x] + 1;
					q.push(realNum);
				}
			}
		}
	}
}

int main() {
	memset(Prime, true, sizeof(Prime));
	findPrime();
	cin >> T;
	int start, dest;
	while (T--) {
		memset(check, -1, sizeof(check));
		cin >> start >> dest;
		bfs(start, dest);
		if (check[dest] == -1)
			cout << "Impossible" << '\n';
		else
			cout << check[dest] << '\n';
	}
	return 0;
}