백준 / BOJ / 1963 소수 경로 C++

www.acmicpc.net/problem/1963

1963번: 소수 경로

간단한 bfs 문제이지만, 초기화를 이상하게 해서 푸는데 20분, 에러 찾는데 1시간이 걸린 문제입니다. 너무 화가 납니다 ㅎㅎㅎ

 

4자리 소수를 한 자리씩 바꿀 수 있고, 이 바꾼 수 또한 소수여야합니다. 그렇게 한 자리씩 바꾼 수가 목표한 수가 될 때까지 수를 바꾼 횟수의 최솟값을 구하면 됩니다.

 

에라토스테네스 체를 이용해 1000~9999까지 소수들을 미리 구해준 뒤, bfs를 이용해 각 자리별로 0~9까지로 바꾼 뒤 4자리 수인지, 소수인지, 이미 거쳐간 수인지 판단하면 됩니다. 

 

그리고 그렇게 바꿀 수 없으면 impossible을 출력합니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;

bool check[10000];
bool prime[10000];
int res;

void make_prime()
{
	memset(check, false, sizeof(check));
	memset(prime, true, sizeof(prime));
	prime[0] = false;
	prime[1] = false;
	for (int i = 2; i < 10000; i++) {
		for (int j = 2; j * i < 10000; j++) {
			prime[j * i] = false;
		}
	}
}

void bfs(int start, int end)
{
	queue<pair<int, int>>q;
	q.push({ start,0 });
	res = -1;

	while (!q.empty()) {

		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();
		check[num] = true;

		if (num == end)
		{
			res = cnt;
			return;
		}

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 10; j++) {
				string s = to_string(num);
				s[i] = j + '0';

				int next = stoi(s);
				if (next < 1000 || next >= 10000)
					continue;
				if (check[next])
					continue;
				if (!prime[next])
					continue;

				q.push({ next,cnt + 1 });
			}
		}
	}
}

int main()
{
	int T;
	cin >> T;

	make_prime();

	while (T--)
	{
		memset(check, false, sizeof(check));
		int start, end;
		cin >> start >> end;

		bfs(start, end);
		if (res == -1)
			cout << "impossible" << '\n';
		else
			cout << res << '\n';
	}
}