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

문제

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

1963번: 소수 경로

문제풀이

A에서 B로 숫자를 바꾸는 과정에서도 항상 소수를 유지해야 한다.

먼저 에라토스테네스의 체를 이용하여 소수를 구한다.

prime벡터는 소수가 아니면 false를, 소수이면 true이다.

숫자를 바꿀 때 임시로 int형에서 string형으로 바꾸고 이중 반복문으로 모든 자리를 0부터 9까지 바꾼다.

바꾼 번호가 목표하는 번호와 같다면 cnt+1을 하여 출력해준다.

그렇지 않다면 다시 int형으로 숫자를 바꾼다.

세 가지 조건인 천의 자리가 0, 처음 만든 수, 소수임을 만족하면 큐에 넣는다.

큐가 빌 때까지 출력이 안되었다면 만들 수 없는 수 이므로 Impossible을 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<bool>prime;

void BFS(int start, string target, vector<bool>visit) {
	int idx = 0;
	int idx2 = 0;
	queue<pair<int, int>>q;
	q.push({ start,0 });
	visit[start] = true;
	while (!q.empty()) {
		int num = q.front().first;
		int cnt = q.front().second;
		q.pop();

		for (idx = 0; idx < 4; ++idx) {
			for (idx2 = 0; idx2 <= 9; ++idx2) {
				string s_num = to_string(num);
				s_num[idx] = (char)(idx2 + 48);
				if (s_num == target) {
					cout << cnt + 1 << '\n';
					return;
				}
				else {
					int n_num = stoi(s_num);
					if (n_num / 1000 != 0 && !visit[n_num] && prime[n_num]) {
						visit[n_num] = true;
						q.push({ n_num, cnt + 1 });
					}
				}
			}
		}
	}
	cout << "Impossible" << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T = 0;
	cin >> T;

	int idx = 0;
	prime = vector<bool>(10000, true);
	int num = 2;

	for (num = 2; num <= 100; ++num) {
		for (idx = 1000 / num; num * idx < 10000; ++idx)
			prime[idx * num] = false;
	}
	vector<bool>visit(10000, false);

	while (T--) {
		int num1 = 0, num2 = 0;
		cin >> num1 >> num2;
		if (num1 == num2) cout << "0\n";
		else
			BFS(num1, to_string(num2), visit);
	}
}