백준 1963 : 소수 경로

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

1. 접근

• 이 비밀번호는 무조건 4자리인데, 4자리 중 어느 자리를 바꿀 것인지에 따라 실행 순서가 달라질 수 있다. 이 경우, 앞선 BFS문제들과 마찬가지로 최소실행을 구해야 하기때문에 BFS가 더 적합하다.
• 숫자를 만들 때마다 소수인지 구할 수도 있지만, t번의 실행을 하기 때문에 처음부터 범위 내의 소수 숫자들을 배열에 미리 찾아놓는다.
• 최소 숫자만 중요하기 때문에, 이미 접근한 적이 있다면 굳이 진행할 필요가 없다.(뒤에 접근하면 무조건 더 큰 수가 들어간다)
  => time 배열을 만들어, 실행 시간을 저장해준다.
• 반복문으로 t번의 실행을 수행할 때, queue와 time 배열의 초기화를 주의하자.
• (앞에서부터) 2번째 자리를 바꾸자! 라는 단순해보이는 기능도, string을 사용하는지, 안하는지에 따라 구현이 달라질 수 있다.
  => 나의 경우, 사용하지 않았다. 숫자를 자릿수마다 분리하고, 다시 합쳐주는 과정을 거쳤다.(조금 비효율적인 것 같다.)

2. 나의 풀이

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int a, b;
queue<int> q;
int timearr[10001];
bool primearr[10001];

void SetPrime() {
	for (int j = 1000; j < 10000; j++) {
		for (int i = 2; i < j / 2; i++) {
			if (j%i == 0) {
				primearr[j] = false;
				break;
			}
		}
	}
	return;
}

int changeAtPosition(int a, int b, int position) {
	int ret = 0;	
	//cout << a << " -> " << b << ", "<<position<<" 위치 변환 ";
	int num[4];
	for (int i = 3; i >=0; i--) {
		num[i] = a % 10;
		a /= 10;
	}
	for (int i=1; i <=4; i++) {
		if (i == position)	ret += b;
		else ret += num[i-1];
		ret *= 10;
	}
	//cout << ret/10 << " 완료\n";

	return ret/10;
}

void BFS(int num) {
	q.push(num);
	timearr[num] = 1;

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

		//cout << now <<" ("<<timearr[num]<<") : ";
		if (now == b) {
			cout << timearr[b]-1 << "\n";
			return;
		}

		for (int i = 1; i <=4; i++) {
			for (int j = 0; j < 10; j++) {
				if (i == 1 && j == 0)	continue;
				
				int next = changeAtPosition(now, j, i);
				if (primearr[next] && timearr[next] == 0) {
					q.push(next);
					timearr[next] = timearr[now] + 1;
					//cout << next << " ";
				}
			}
		}
		//cout << "\n";
	}
	cout << "Impossible\n";
}

void init() {
	while (!q.empty()) {
		q.pop();
	}
	memset(timearr, 0, sizeof(timearr));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	memset(primearr, true, sizeof(primearr));
	SetPrime();

	for (int i = 0; i < t; i++) {
		cin >> a >> b;
		init();
		BFS(a);
	}
	return 0;
}