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

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

 

코드

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

#define MAX 10001
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

typedef pair<int, int> pi;
bool isPrime[MAX], visit[MAX];
int change[4] = { 1000, 100, 10, 1 };

void checkPrime() {
	memset(isPrime, true, sizeof(isPrime));
	for (int i = 2; i*i<MAX; i++) {
		if (isPrime[i]) {
			for (int j = i * i; j < MAX; j += i)
				isPrime[j] = false;
		}
	}
}

void bfs(int now, int goal) {
	queue<pi> q;

	q.push({ now, 0 });
	visit[now] = true;

	while (!q.empty()) {
		int value = q.front().first;
		int cnt = q.front().second;
		q.pop();

		if (goal == value) {
			cout << cnt << "\n";
			return;
		}

		for (int i = 0, tmp; i < 4; i++) {
			tmp = value;
			int p = (value / change[i]) % 10;
			tmp -= (p * change[i]);

			for (int j = 0; j < 10; j++) {
				if (i == 0 && j == 0) continue;
				int next = tmp + j * change[i];
				if (next >= 1000 && next <= 9999 && !visit[next] && isPrime[next]) {
					q.push({ next, cnt + 1 });
					visit[next] = true;
				}
			}
		}
	}
	cout << "Impossible\n";
}

int main() {
	FASTIO;
	int t, a, b;
	cin >> t;

	checkPrime();
	
	while (t--) {
		cin >> a >> b;
		bfs(a, b);
		memset(visit, false, sizeof(visit));
	}
	return 0;
}

설명

필요한 변수를 입력받은 후 checkPrime 함수로 미리 천의 자리 수까지 소수 판별을 합니다. 이후 테스트케이스마다 현재의 값, 바꾸고자 하는 값을 입력받은 후, 이에 대해서 bfs 함수를 호출합니다. 

 

bfs 함수에서는 기본적으로 큐에  현재의 값과 처음의 값에서 현재 값까지 오는 데 필요한 횟수를 저장해두고 이를 이용합니다.  for문 내에서는 천의 자리부터 일의 자리까지 값을 전부 다 바꿔보면서 천의 자리 소수이면서 방문하지 않은 값에 대해서만 큐에 넣어줍니다.

 

목표하는 값에 도달하였다면 오는 데 걸리는 횟수를 출력하고, 큐가 빌 때까지 도달하지 못했다면 Impossible을 출력하면 됩니다.

 

느낀 점

소수를 에라토스테네스의 체로 미리 판별해둔 후, 자릿수를 하나 바꿨을 때에도 소수일 경우에 대해서만 BFS를 돌리면 됩니다!