백준 1963번: 소수 경로

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

1963번: 소수 경로

아이디어 :
1. 에라토스테네스의 체를 통해 10000이하 소수를 구한다.

2. 한 자리 씩 바꿔가며, 소수가 가능한 경우의 수를 큐에 넣는다.

3. BFS를 돌린다.

의견 : 한국어를 못해서 그런건지 문제를 이해하는데 오랜 시간이 걸렸다.
그래서 1033->1733 사이에만 소수가 많아서, 어떤게 바로 100의 자리를 7로 바꾸는 거지? 이 생각을 했었다.
그냥  다 무식하게 BFS 돌렸다 가능한 애들만 큐에 넣어서!

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

using namespace std;

int T;
int* pnArr;
int nCount[10000];

vector<int> v;

void InitPrime(void)
{
	pnArr = (int*)malloc(sizeof(int*) * 10000);
	
	for (int i = 2; i < 10000; i++)
	{
		pnArr[i] = i;
	}

	for (int i = 2; i < 10000; i++)
	{
		if (pnArr[i] == 0)
		{
			continue;
		}
		for (int j = i + i; j < 10000; j+= i)
		{
			pnArr[j] = 0;
		}
	}
}

void BFS(int nStart, int nDest, int nDepth)
{
	memset(nCount, 0, sizeof(nCount));

	queue<int> q;
	q.push(nStart);

	while (!q.empty())
	{
		int nSize = q.size();

		for (int i = 0; i < nSize; i++)
		{
			int nTemp = q.front();
			q.pop();

			if (nTemp == nDest)
			{
				return;
			}

			string strNum = to_string(nTemp);
			for (int j = 0; j < 4; j++)
			{
				string strTemp = string(strNum);
				for (int k = '0'; k <= '9'; k++)
				{
					strTemp[j] = k;
					int nTest = stoi(strTemp);
					if (pnArr[nTest] && !nCount[nTest] && nTest >= 1000)
					{
						nCount[nTest] = 1;
						q.push(nTest);
					}
				}
			}
		}

		v[nDepth]++;
	}
}
int main(void) 
{
	cin >> T;

	int nFrom, nTo;
	
	InitPrime();

	v.assign(T, 0);

	for (int i = 0; i < T; i++)
	{
		cin >> nFrom >> nTo;
		BFS(nFrom, nTo, i);
	}

	for (int i = 0; i < T; i++)
	{
		cout << v[i] << endl;
	}

	free(pnArr);

	return 0;
}