[백준 1963] 소수 경로 (C++)

문제 링크: https://www.acmicpc.net/problem/1963

1963번: 소수 경로

1. 주의할 점

- '에라토스테네스의 체'를 통해 미리 4자리의 소수를 구해놓는다

- BFS를 통해 4자리 모두 0~9까지 돌려보면서 구한다

 

2. 구현

- 에라토스테네스의 체가 적용된 Cal() 함수를 통해 4자리의 소수를 Prime 벡터에 담아놓는다

- 매 TC마다 4자리 자연수의 Visit값을 False로 만든 후, 4자리의 소수중 소수인것의 Visit값을 True로 다시 전환한다

- Queue에 Start를 넣고 Visit[Start] = True로 바꾼 후 While문을 수행한다

- Len을 통해 현재 Queue에 들어 있는 원소만큼 모든 수를 돌린다(몇 번만에 Dest번호에 도달했는지 최소 값을 구하기 위해)

- Queue에서 숫자를 빼면서 4자리 모두 0~9를 한번씩 돌리고, 도출된 수의 Visit값이 참이라면(소수지만 아직 도달하지 않은 수) 큐에 넣는다

- 위의 2개 작업을 Queue의 원소 중, Dest가 나오거나 Queue가 비었을 때까지 수행한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
vector<int> prime;
int isPrime[10000];
bool visit[10000];
int mul[4] = { 1000,100,10,1 };

void cal() {
	for (int i = 2; i < 10000; i++)
		isPrime[i] = i;
	for (int i = 2; i < 10000; i++) {
		if (isPrime[i] == 0) continue;		
		for (int j = i * 2; j < 10000; j += i)
			isPrime[j] = 0;	
	}
	for (int i = 2; i < 10000; i++) {
		if (isPrime[i] != 0 && i >= 1000)
			prime.push_back(i);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cal();
	int num, start, dest;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> start >> dest;
		for (int j = 1000; j < 10000; j++)
			visit[j] = false;
		for (int j = 0; j < prime.size(); j++)
			visit[prime[j]] = true;
		queue<int> q;
		visit[start] = false;
		int cnt = 0;
		q.push(start);
		bool finish = false;
		while (!q.empty()) {
			int len = q.size();
			for (int k = 0; k < len; k++) {
				int cidx = q.front();
				q.pop();
				if (cidx == dest) {
					finish = true;
					break;
				}
				for (int m = 0; m < 4; m++) {
					int temp = 0;
					if (m == 0) temp = cidx % 1000;
					else if (m == 1) {
						temp = cidx / 1000;
						temp *= 1000;
						temp += cidx % 100;
					}
					else if (m == 2) {
						temp = cidx / 100;
						temp *= 100;
						temp += cidx % 10;
					}
					else if (m == 3) {
						temp = cidx / 10;
						temp *= 10;
					}
					int add;
					for (int l = 0; l < 10; l++) {
						add = mul[m] * l;
						add += temp;
						if (visit[add]) {
							visit[add] = false;
							q.push(add);
						}
					}
				}
			}
			if (finish)
				break;
			cnt++;
		}
		if (finish) cout << cnt << '\n';
		else cout << "Impossible\n";
	}
	system("pause");
	return 0;
}