[백준문제풀이] 1963 소수 경로

 

풀이일시 : 2020-11-15

​

 

문제 :

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

-----

“이제 슬슬 비번 바꿀 때도 됐잖아”

“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"

“그럼 8179로 해”

“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”

“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”

“귀찮아”

-----

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

​

 

입력 :

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

ex)

3

1033 8179

1373 8017

1033 1033

​

​

출력 :

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

ex)

6

7

0

​

​

풀이 :

4자리 소수를 소수로 바꾸는데 한글자씩 바꿀 수 있다. 그 과정에서 거쳐가는 모든 수가 소수여야한다.

-> 소수판별알고리즘 (에라토스테네스의 체를 사용할 것) 으로 범위내의 소수들을 우선 파악해 놓는다.

-> 탐색 알고리즘 BFS를 사용하여 숫자를 바꿔주며 큐에 넣어주고 그게 소수인지,방문하였는지 여부, 목표값인지 확인하며 BFS를 계속하여 실행해준다.

-> 숫자를 바꿔주는 과정에서 주의할 점은 천의자리 숫자이냐 아니냐 이다. 1000미만의 비밀번호가 허용되지 않기 때문에 천의자리 숫자에는 0이 들어갈 수 없기 때문이다.

 

참고자료 : 

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색

dbstndi6316.tistory.com/53

[기본문제풀이] 에라토스테네스의 체

 

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring> //memset 을 위해서
#define MAX 10000
using namespace std;

int a[MAX];
int prime[MAX]; //소수판별을 통해 소수가 저장되는 배열
int start, destination;
int cache[MAX];

//에라토스테네스의 체 로 소수판별해놓기
void primeNumberSieve() {
	//각자의 수로 초기화해준다.
	for (int i = 2; i <= MAX; i++) {
		a[i] = i;
	}
	//2부터 소수가 아닌것들을 0으로 변환시켜준다.
	for (int i = 2; i <= MAX; i++) {
		if (a[i] == 0)
			continue;
		for (int j = i + i; j <= MAX; j += i) {
			a[j] = 0;
		}
	}
	for (int i = 2; i <= MAX; i++) {
		if (a[i] != 0)
			prime[i] = i;
	}
}

int BFS(void)
{
	memset(cache, 0, sizeof(cache));
	queue<int> q;
	q.push(start);
	cache[start] = 1;

	while (!q.empty())
	{
		int curNum = q.front();
		q.pop();
		if (curNum == destination)
			return cache[curNum] - 1;
		//현재 숫자 천의 자리숫자부터
		int digit[4] = { curNum / 1000, (curNum / 100) % 10, (curNum / 10) % 10, curNum % 10 };
		//1333 이라면 ( 1, 3, 3, 3 ) 으로 분리된다.
		for (int i = 0; i < 4; i++)
		{
			//천의 자리 수는 0이면 안된다 여기서는 1033 2033 ~9033 까지 바뀐다.
			if (i == 0)
			{
				for (int j = 1; j < 10; j++) // 천의자리수가 0이면 안되니깐
				{
					int changeNum = 0;
					for (int k = 0; k < 4; k++) // 0, 1, 2, 3 번째 자리의 수
						if (i != k)
							changeNum += digit[k] * pow(10, 3 - k);
						else
							changeNum += j * pow(10, 3 - k);
					//바뀐 숫자가 소수이고 방문하지(cache) 않았다면 +1하여 push.
					if (prime[changeNum] == changeNum && cache[changeNum] == 0)
					{
						cache[changeNum] = cache[curNum] + 1; //이 과정을 통해 수행횟수를 센다.
						q.push(changeNum);
					}
				}
			}
			//천의자리수가 아닐때 여기서는 백, 십, 일의 자리수가 바뀐다.
			else
			{
				for (int j = 0; j < 10; j++)
				{
					int changeNum = 0;
					for (int k = 0; k < 4; k++)
						if (i != k)
							changeNum += digit[k] * pow(10, 3 - k);
						else
							changeNum += j * pow(10, 3 - k);
					//바뀐 숫자가 소수이고
					if (prime[changeNum] == changeNum && cache[changeNum] == 0)
					{
						cache[changeNum] = cache[curNum] + 1; //이 과정을 통해 수행횟수를 센다.
						q.push(changeNum);
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	int casecount;
	cin >> casecount;
	primeNumberSieve();

	for (int i = 0; i < casecount; i++) {
		cin >> start >> destination;
		int fin = BFS();
		if (fin == -1)
			cout << "Impossible" << endl;
		else
			cout << fin << endl;
	}
	return 0;
}