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

문제 링크

1963번: 소수 경로

문제 요약

한 네 자리 소수에서 다른 네 자리 소수로 이동을 해야 한다. 이동을 할 때는 네 자리 수의 각 자리에서 숫자를 하나씩 바꿔야 하는데, 이동 과정에 만나는 수들도 모두 소수이며 네 자리 수가 되어야 한다. 이 때, 다른 네 자리 소수로 이동하기 위한 최소 이동 횟수를 구해야 한다.

접근 방법

간단한 BFS 응용 문제입니다. 각 소수들을 정점으로 생각하면, 한 자리의 숫자를 바꿔서 같아지는 소수들 사이에는 간선이 있다고 생각해 볼 수 있습니다. 그러면 BFS를 통해서 간단하게 최단경로를 구할 수 있습니다. 네 자리 소수의 수도 그렇게 많지는 않기 별다른 제약은 없습니다.

에라토스테네의 체를 이용해서 네 자리 소수를 전처리로 구해놓고, BFS를 돌리면 됩니다.

자릿수를 바꾸는 절차는 수를 문자열로 바꿔서 처리하면 간단하게 처리할 수 있습니다. 문자열로 바꿔서 반복문으로 4개의 자릿수에 접근하고, 0부터 9까지를 다 넣어보는 식으로 작성하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int n, d;
};

const int MAX = 10000;
bool visited[MAX], check[MAX];

void init(void) {
	for (int i = 2; i * i < MAX; i++)
		if (!check[i])
			for (int j = i * 2; j < MAX; j += i)
				check[j] = true;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	init();

	int t;
	cin >> t;

	while (t--) {
		int n1, n2;
		cin >> n1 >> n2;

		queue<Data> q;
		q.push({ n1, 0 });
		memset(visited, false, sizeof(visited));

		int dist = -1;
		while (!q.empty()) {
			auto now = q.front();
			q.pop();

			if (now.n == n2) {
				dist = now.d;
				break;
			}

			string str = to_string(now.n);

			for (int i = 0; i < 4; i++) {
				string tmp = str;
				for (char j = '0'; j <= '9'; j++) {
					tmp[i] = j;
					int next = stoi(tmp);

					if (next >= 1000 && next <= 9999 && !check[next] && !visited[next]) {
						visited[next] = true;
						q.push({ next, now.d + 1 });
					}
				}
			}
		}

		if (dist == -1)
			cout << "impossible\n";
		else
			cout << dist << '\n';
	}

	return 0;
}