[백준]Baekjoon1963(BFS,큐)

문제링크 : https://www.acmicpc.net/problem/1963

풀이

어떻게 풀어야하나 고민을 많이 했는데 결론적으로는 큐를 이용해 

일일히 다 검사하면서 문제를 풀었다.

먼저 해결해야 하는것은 4자리 수중에 소수들을 가려내는 작업이다.

이 작업은 에라토스테네스의 체를 이용하여 소수들을 선별해놓으면 편하다.

에라토스테네스의 체에 대해 자세히 모른다면

http://dolphins-it.tistory.com/105?category=771381 을 참조하자

아무튼 이러한 방식으로 소수를 판별했다면

자릿수 별로 숫자를 바꿔주면서 해당 자릿수의 숫자를 바꿨을 때 소수이면서

방문하지 않은 숫자라면 큐에 삽입해서 원하는 수가 나올 때까지 계속 반복해주도록 한다.

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int memo[10001]; //에라토스테네스의 체를 통해 소수판별
bool visit[10001]; //방문한 수인지 판별

void eratosthenes() //에라토스테네스의 체
{
	for (int i = 2; i <= 100; i++) {
		if (!memo[i]) {
			for (int j = i*i; j <= 10000; j += i) {
				memo[j] = true;
			}
		}
	}
}
int main()
{
	int testcase;
	scanf("%d", &testcase);
	eratosthenes();

	while (testcase--) {
		int a, b;
		scanf("%d %d", &a, &b);
		queue<pair<int, int>>  q; //첫번 째 인자는 4자리 숫자, 두번째 인자는 변환한 횟수이다.
		q.push(make_pair(a, 0));
		memset(visit, 0, sizeof(bool) * 10001); //visit배열 초기화
		for (int i = 0; i < 1000; i++) visit[i] = 1;//1000 미만의 수는 취급하지 않으므로 그냥 방문했다고 설정해둔다.

		while (!q.empty()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			visit[x] = true;
			if (x == b) { printf("%d\n", y);
			break;
			}
			for (int i = 0; i < 4; i++) { //1의자릿수~ 1000의 자릿수까지 순서대로 바꿔주기 위한 반복문
				int div = (int)pow(10, i);
				int tmp = ((x / div) % 10) * div;
				for (int j = 0; j < 10; j++) { //해당 자릿수를 0~9까지 모두 바꿔가며 검사
					int num = x - tmp + (j*div);
					if (!visit[num] && !memo[num]) //아직 방문하지 않았고 소수라면
						q.push(make_pair(num, y + 1));
				}
			}
		}
	}
}