[bfs] 백준 1963 소수 경로

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

1963번: 소수 경로

소수는 에라토스테네스의 채를 이용해서 구했습니다.

처음에 풀 때는 queue에 넣을 값을 찾기 위해 1000부터 9999까지 모두 뒤졌습니다. 당연하게도  시간초과가 뜨더군요.

 

그래서 1,10,100,1000 자리의 숫자만 변경하는 것으로 하니 잘 되네요.

 

#include <iostream>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
bool num[10000] = { 0 };

void num_set() {

	for (int i = 2; i <= sqrt(9999); i++) {
		if (!num[i]) {
			for (int j = i + i; j <= 9999; j += i)
				num[j] = true;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(false);
	num_set();
	int t;
	cin >> t;

	while (t--) {
		string x, y;
		int cnt = -1;
		bool chk = false;
		queue<string> q;
		bool visited[10000] = { 0 };

		cin >> x >> y;
		q.push(x); visited[atoi(x.c_str())] = true;

		while (!q.empty()) {
			cnt++;
			int size = q.size();
			
			for (int i = 0; i < size; i++) {
				string tmp = q.front(); q.pop();

				if (tmp == y) {
					chk = true; break;
				}

				for (int j = 0; j < 4; j++) {
					for (int k = 0; k <= 9; k++) {
						string dtmp = tmp;
						dtmp[j] = k + 48;
						if (visited[atoi(dtmp.c_str())]) continue;
						if (num[atoi(dtmp.c_str())]) continue;
						if (atoi(dtmp.c_str()) < 1000) continue;
						q.push(dtmp);
						visited[atoi(dtmp.c_str())] = true;
					}
				}

			}
			if (chk) break;
		}

		if (chk) cout << cnt << endl;
		else    cout << "Impossible" << endl;
	}

}