1963번 소수 경로

• 코딩 스킬
  에라토스테네스의 체라는게 있다. 소수를 찾을 때 빠르게 구할 수 있다.
  배열의 초기값이 false라 조금 헷갈릴 수도 있는데... 어떤 수가 소수라면(초기값은 false), 그 수의 배수는 다 소수가 아니다. 그래서 반대로 true로 설정해준다. 다 돌면 반대로 뒤집어서 제대로 표현한다!

#include <iostream>

using namespace std;
bool prime[10001];
int main() {
	for (int i = 2; i <= 10000; i++) {
		if (prime[i] == false) {
			for (int j = i * i; j <= 10000; j += i) {
				prime[j] = true;
			}
		}
	}
	for (int i = 0; i <= 10000; i++) prime[i] = !prime[i];
	for (int i = 1; i <= 1000; i++) cout << prime[i] << " ";
	return 0;
}

약간은 복잡할 수 있다. 4자리 자물쇠를 떠올려보면 이해가 쉬울 것 같다.
일단 처음 입력받은 비밀번호를 각 자리수마다 0~9까지 돌려본다(이때 제일 앞이 0이 오면 안된다). 돌려본 숫자가 소수가 아니면 넘기고, 소수면 체크배열에 체크하고 거리배열(dis)에 담고 +1해준다. 그러면 최종 비밀번호가 들어왔을때, 거리배열[최종비밀번호]를 출력해주면 된다.

#include <iostream>
#include <string>
#include <queue>
#include <string.h>
using namespace std;
bool prime[10001];
int ch[10001];
int dis[10001];
int change(int num, int index, int digit) {
	if (index == 0 && digit == 0) return -1;
	string s = to_string(num);
	s[index] = digit + '0';
	return stoi(s);
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	for (int i = 2; i <= 10000; i++) {
		if (prime[i] == false) {
			for (int j = i * i; j <= 10000; j += i) {
				prime[j] = true;
			}
		}
	}
	for (int i = 0; i <= 10000; i++) prime[i] = !prime[i];
	int n, m, cnt;
	cin >> cnt;
	while (cnt--) {
		cin >> n >> m;
		memset(dis, 0, sizeof(dis));
		memset(ch, 0, sizeof(ch));
		dis[n] = 0;
		ch[n] = 1;
		queue<int> Q;
		Q.push(n);
		while (!Q.empty()) {
			int tmp = Q.front();
			Q.pop();
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j <= 9; j++) {
					int next = change(tmp,i,j);
					if (next == -1) continue;
					if (prime[next] == false) continue;
					if (ch[next] == 0) {
						ch[next] = 1;
						dis[next] = dis[tmp]+1;
						Q.push(next);
					}
				}
			}
		}
		cout << dis[m] << '\n';
	}
	return 0;
}