BOJ : 1963 소수 경로

 

---

[BOJ 1963(G5) 리뷰]

네자리의 소수로 된 비밀번호를 다른 네자리의 소수로 바꾸려고 한다.
그러나 바꿀때는 한 자리씩 밖에 변경할 수 없고 한자리씩 바꾸었을때의 네자리 역시 소수여야 한다.
기존 비밀번호와 바꾸고자 하는 비밀번호가 주어질때 원하는 비밀번호까지 최소 몇번의 단계를 거쳐야 하는지 출력해야 하는 문제이다.

우리는 원하는 비밀번호까지의 최소 단계를 구해야 하므로 BFS로 접근해야 한다.
BFS를 수행하기 전에 소수 확인 작업을 O(1)에 처리하기 위하여 먼저 1000~9999의 숫자에 대해 소수판별 작업을 거쳤다.그 후에 현재 비밀번호의 첫번재 자리부터 네번째 자리까지에 0~9의 수를 넣어보고 넣어봤을때의 숫자가 소수라면 큐에 넣고 이어서 탐색하도록 하면 된다.

처음엔 코드가 비효율적이라 생각하여 시간초과가 나지 않을까 했는데 우리는 1000~9999의 숫자들만 확인하면 되므로 시간초과는 나지 않았다.

---

/*
	20.09.15
	BOJ : 1963 소수 경로 (https://www.acmicpc.net/problem/1963)
	그래프 탐색
*/
#include <bits/stdc++.h>
using namespace std;

bool isValid[10000];
int dist[10000];
int main()
{
	//소수 판별
	for (int val = 1000; val <= 9999; val++)
	{
		int ret = true;
		for (int i = 2; i <= sqrt(val); i++)
		{
			if (val % i == 0)
			{
				ret = false;
				break;
			}
		}
		if (ret)
			isValid[val] = 1;
	}
	
	int T;
	cin >> T;
	while (T--)
	{
		int start, end;
		cin >> start >> end;
		fill(dist, dist + 10000, -1);
		queue<int>Q;
		Q.push(start);
		dist[start] = 0;
		
		while (!Q.empty())
		{
			int cur = Q.front(); Q.pop();
			
			for (int i = 0; i < 4; i++)
			{
				string node = to_string(cur);
				for (int j = 0; j < 10; j++)
				{
					node[i] = j + '0';
					int next = stoi(node);
					if (next < 1000 || isValid[next] == 0 || dist[next] != -1) continue;
					Q.push(next);
					dist[next] = dist[cur] + 1;
				}
			}
		}

		if (dist[end] == -1)
			cout << "Impossible\n";
		else
			cout << dist[end]<<'\n';
	}

	

	
}