[C/C++] 백준 - 1963번 : 소수 경로

https://www.acmicpc.net/problem/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을 출력한다.

 

4자리 정수 2개가 주어졌을 때, 첫번째 소수에서 두번째 소수로 한자리씩 수를 변경하고자 할 때 필요한 최소의 변환 횟수를 구하는 문제이다.

예전에 풀었었던 숨박꼭질 문제와 비슷하다는 생각이 들었고, BFS로 해결이 가능하다고 판단이 들었다.

 

그럼 어떻게 할거냐?

문제에서 하라는 대로 4자리 수 중 한자리만 변경이 가능하므로 천의 자리 숫자부터 일의 자리 숫자까지

현재와 다른 수로 자리수 하나만 변경시키고, 그 값의 변경 최소

횟수를 메모이제이션으로 저장해주는 방법으로 해결하였다.

 

그리고 소수는 에라토스테네스의 체 알고리즘 기법으로 저장해주었다

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

int max_n = 9999;
int Prime[10000];
int visited[10000];

void go_Prime() {
	for (int i = 2; i <= max_n; i++) Prime[i] = i;
	for (int i = 2; i <= max_n; i++) {
		for (int j = i + i; j <= max_n; j += i) {
			if (!Prime[j]) continue;
			Prime[j] = 0;
		}
	}
}

int go_Change(int a, int b) {
	for (int i = 1000; i <= 9999; i++) visited[i] = INF;
	queue<int> q;
	q.push(a);
	visited[a] = 1;

	while (!q.empty()) {
		int y = q.front();
		q.pop();
		if (y == b) return visited[y] - 1;

		string Temp = to_string(y);
		string tmp = Temp;
		int cur = Temp[0] - '0';
		for (int i = 1; i <= 9; i++) {
			if (i == cur) continue;
			tmp[0] = i + '0';
			if (Prime[stoi(tmp)] != 0 && visited[y]+1 < visited[stoi(tmp)]) {
				q.push(stoi(tmp));
				visited[stoi(tmp)] = min(visited[stoi(tmp)], visited[y] + 1);
			}
		}
		tmp = Temp;
		cur = Temp[1] - '0';
		for (int i = 0; i <= 9; i++) {
			if (i == cur) continue;
			tmp[1] = i + '0';		
			if (Prime[stoi(tmp)] != 0 && visited[y] + 1 < visited[stoi(tmp)]) {
				q.push(stoi(tmp));
				visited[stoi(tmp)] = min(visited[stoi(tmp)], visited[y] + 1);
			}
		}
		tmp = Temp;
		cur = Temp[2] - '0';
		for (int i = 0; i <= 9; i++) {
			if (i == cur) continue;
			tmp[2] = i + '0';
			if (Prime[stoi(tmp)] != 0 && visited[y] + 1 < visited[stoi(tmp)]) {
				q.push(stoi(tmp));
				visited[stoi(tmp)] = min(visited[stoi(tmp)], visited[y] + 1);
			}
		}
		tmp = Temp;
		cur = Temp[3] - '0';
		for (int i = 0; i <= 9; i++) {
			if (i == cur) continue;
			tmp[3] = i + '0';
			if (Prime[stoi(tmp)] != 0 && visited[y] + 1 < visited[stoi(tmp)]) {
				q.push(stoi(tmp));
				visited[stoi(tmp)] = min(visited[stoi(tmp)], visited[y] + 1);
			}
		}
	}
	return -1;
}

int main() {
	CUNLINK;
	go_Prime();
	
	int testCase;
	cin >> testCase;
	string fail = "Impossiible";

	while (testCase--) {
		int First, Second;
		cin >> First >> Second;
		int Cnt = go_Change(First, Second);
		if (Cnt == -1) cout << fail << endl;
		else cout << Cnt << endl;
	}

	return 0;
}