BaekJoon 1963 소수경로

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

소스결과 1996 KB / 0 ms

출처 Baekjoon, NWERC 2006

언어 C++ 17

분류 BFS 소수

 

설명

소수를 좋아하는 창영이가 4자리 소수인 현재 비밀번호를 다른 4자리 소수인 비밀번호로 바꾸려고 할 때. 한번에 한 자리씩 바꾸어서 다른 비밀번호가 되는 최소의 경우의 수를 출력한다.

 

소수에 집착하는 창영이 그리고 비밀번호를 한 번에 한 자리 밖에 못바꾸는 괴상망측한 게임. 현실에서는 절대 보기 힘든 조합이다.

먼저 현재 값이 소수인지 판별 하기 위한 방법이 필요하다. 탐색의 경우가 여러 번 존재하기 때문에 소수를 판별해 줄 부분이 필요하다.

범위가 최대 9999 이기에 에라토스테네스의 체를 이용해 소수를 미리 구해두자.

한번에 한 자리를 바꿀 수 있기 때문에 1천의 자리 1백의 자리 1십의 자리 1의자리 4부분으로 나누어 총 39번을 확인한다.

하지만 39번 전체가 소수가 아니기에 많아봐야 3번정도로 줄어든다.

Queue에 들어가는 경우는 한 자리를 바꾼 수가 소수인지, 일전에 탐색 했던 숫자인지 판별해 만족하는 조건 일 때에만 Queue에 넣는다.

 

알고리즘

1. 에라토스테네스의 체를 이용해 0 ~ 9999 까지의 소수 배열을 미리 만들어 둔다.

2. 초기 값을 기준으로 각각의 자리를 변경 했을 때 소수 이면서 탐색 되지 않은 값을 Queue에 넣는다.

3. Queue에서 꺼낸 값이 목표 값과 일치하면 탐색을 종료한다.

4. 출력

 

소스코드

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAX = 10000;
const int RANGE_MAX = 9000;
bool prime[MAX + 1];

void init()
{
	prime[0] = prime[1] = true;

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

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

int main()
{
	int tcc = 0;

	cin >> tcc;

	init(); // prime Init

	for (int i = 0; i < tcc; i++)
	{
		int start, des;
		int count = 0;
		queue<int> q;
		queue<int> nextQ;
		bool isOver = false;
		bool check[RANGE_MAX];
		memset(check, false, sizeof(check));

		cin >> start >> des;

		q.push(start);
		check[start] = true;

		while (!q.empty())
		{
			while (!q.empty())
			{
				int cur = q.front();
				q.pop();

				if (cur == des)
				{
					isOver = true;
					break;
				}

				int posMax = 10000;
				int posMin = 1000;

				for (int i = 0; i < 4; i++)
				{
					for (int j = 0; j < 10; j++)
					{
						if (i == 0 && j == 0)
							continue;

						int cal = ((cur / posMax) * posMax) + (j * posMin) + (cur % posMin);

						if (!prime[cal] && !check[cal-1000])
						{
							check[cal-1000] = true;
							nextQ.push(cal);
						}
					}
					posMax /= 10;
					posMin /= 10;
				}
			}

			if (isOver)
				break;
			else
			{
				while (!nextQ.empty())
				{
					q.push(nextQ.front());
					nextQ.pop();
				}
				++count;
			}
		}
		cout << count << '\n';
	}
	
	return 0;
}