1963번: 소수 경로

문제링크: 1963번: 소수 경로

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

설명

소수로 시작해서 소수로 이동하고 소수로 도착하는 문제인데 수의 범위가 9999까지이기 때문에 기본적으로 1부터 9999까지 소수판별을 해야한다.

소수판별을 위해 가장 많이 사용되는 에라토스테네스의 체로 소수판별 배열을 만들어주고 숫자에 대한 그래프 탐색을 진행하였다.

쉬운탐색을위해 입력값을 문자열로 받았고 stoi를 사용해 숫자변환을 쉽게하였다. 탐색은 BFS를 사용하였고 도착문자에 도착하면 횟수 출력을, 도착하지 못하면 Impossible을 출력하도록 하였다.

코드

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#define endl '\n'
#define MAX 10000

using namespace std;

bool prime[MAX];

void createPrime() {
	memset(prime, true, sizeof(prime));

	for (int i = 2; i < MAX; ++i) {
		if (prime[i] == false) continue;

		for (int j = i * 2; j < MAX; j += i) {
			prime[j] = false;
		}
	}
}

void solve() {
	string start, end;
	cin >> start >> end;

	bool check[MAX] = { false };
	queue<pair<string, int>> q;
	q.push({ start,0 });
	while (!q.empty()) {
		string now = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (now == end) {
			cout << cnt << endl;
			return;
		}

		string next;
		for (int l = 0; l < now.size(); ++l) {
			next = now;
			for (int i = 0; i < 10; ++i) {
				next[l] = '0' + i;
				if (check[stoi(next)] || prime[stoi(next)]==false) continue;
				if (stoi(next) < 1000) continue;
				q.push({ next,cnt + 1 });
				check[stoi(next)] = true;
			}
		}
	}
	cout << "Impossible" << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	createPrime();
	int T;
	cin >> T;
	while (T--)
		solve();
	return 0;
}