[BOJ] 백준 1963 소수 경로

[문제]

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

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static int a,b;
	static boolean[] prime = new boolean[10000];
	public static void main(String[] args) throws IOException {
		isPrime();
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int t = Integer.parseInt(br.readLine());
    	while(t-->0) {
    		st = new StringTokenizer(br.readLine());
    		a = Integer.parseInt(st.nextToken());
        	b = Integer.parseInt(st.nextToken());
        	
        	int[] check = new int[10000];
        	Arrays.fill(check, -1);
        	Queue<Integer> q = new LinkedList<>();
        	q.offer(a);
        	check[a] = 0;
        	while(!q.isEmpty()) {
        		int num = q.poll();
        		for(int i=0;i<4;i++) {
        			for(int j=0;j<=9;j++) {
        				if(i==3 && j==0) continue;
        				
        				int[] numArr = makeArr(num);
        				numArr[i] = j;
        				int numM = makeNum(numArr);
        				
        				if(check[numM]!=-1 || !prime[numM]) continue;
        				check[numM] = check[num] + 1;
        				q.offer(numM);
        			}
        		}
        	}
        	if(check[b]==-1) System.out.println("impossible");
        	else System.out.println(check[b]);
    	}  
	}
	private static void isPrime() {
		Arrays.fill(prime,true);
		prime[1] = false;
		for(int i=2;i*i<10000;i++) {
			if(!prime[i]) continue;
			for(int j=i*i;j<10000;j+=i) {
				prime[j] = false;
			}
		}
	}
	private static int[] makeArr(int num) {
		int[] arr = new int[4];
		for(int i=0;i<4;i++) {
			arr[i] = num % 10;
			num /= 10;
		}
		return arr;
	}
	private static int makeNum(int[] arr) {
		int digit = 1;
		int num = 0;
		for(int i=0;i<4;i++) {
			num += arr[i] * digit;
			digit *= 10;
		}
		return num;
	}
}