[BOJ] 백준 1963번 : 소수 경로 C++ : 아주정은

처음에 이문제를 봤을때, 무슨 문제가 이렇게 랏같지? 했다.

이게 소수인지 아닌지 어떻게 판단하지? 라는 생각을 했다. 

소수인지만 판단하면 BFS를 통해서 두번째 입력받은 숫자를 찾는다면, break해주면 된다.

소수인지 판단하는것은 2부터 자신의 수/2까지 나누었을때, 나머지가 없으면 소수가 아닌것이다.

소스코드는 좀 더러울 수 있는데, 참고하고 피드백 항상 환영한다.

#include <iostream>
#include <queue>

using namespace std;

struct Que {
	int x;
	int time;
};


bool is_prime_number(int input) {
	int last = input / 2;
	for (int i = 2; i <= last; i++) {
		if (input%i == 0) return false; // 하나라도 나누어 떨어지면 return false;
	}
	return true;
}


void BFS(int num1, int num2) {
	queue<Que> Q;
	bool vis[10000];
	
	fill(vis, vis+sizeof(vis), false);
	
	Q.push({ num1,0 });
	vis[num1] = true;
	//num1의 숫자를 하나씩 바꿔주면서 큐에 넣어도되는지 판단한다.
	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();
		if (cur.x == num2) {
			cout << cur.time << endl;
			break;
		}
		int current = cur.x;
		int arr[4], copy[4];
		for (int i = 0; i < 4; i++) {
			arr[i] = current % 10;
			copy[i] = arr[i];
			current = current / 10;
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 10; j++) {
				arr[i] = j;

				int next = arr[3] * 1000 + arr[2] * 100 + arr[1] * 10 + arr[0];
				if (vis[next] == true or next == cur.x or arr[3] == 0) continue;
				if (is_prime_number(next)) {
					Q.push({ next,cur.time + 1 });
					vis[next] = true;
				}
			}
			arr[i] = copy[i];
		}

	}
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t, num1,num2;
	cin >> t;
	
	while (t--) {
		cin >> num1 >> num2;
		
		BFS(num1, num2);

	}

}