백준 1963번 소수 경로 (JAVA)

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

1963번: 소수 경로

 

저는 해당 문제를 BFS를 통해 한 자리씩 변경하면서 몇번만에 해당 숫자로 변하는지 확인하였습니다.

isPrime을 통해 1000 ~ 9999까지 해당 숫자가 소수인지를 파악하였고 1000 전까지의 숫자는 false를 줌으로써 BFS에 들어가지 못하게 처리하였습니다.

 

package BOJ.BFS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1963 {

    public static void main(String[] args) throws Exception  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int test = stoi.apply(st.nextToken());
        boolean[] isPrime = new boolean[10_000];
        for(int i = 1_000; i < 10_000 ; i++){
            isPrime[i] = checkPrime(i);
        }
        for(int t = 0 ; t < test ; t++){
            st = new StringTokenizer(br.readLine());
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            int result = bfs(a,b,isPrime);
            if(result == -1){
                System.out.println("Impossible");
            }else{
                System.out.println(result);
            }

        }
    }

    private static boolean checkPrime(int num) {
        for(int i = 2 ; i <= Math.sqrt(num); i++){
            if(num % i== 0){
                return false;
            }
        }
        return true;
    }

    private static int bfs(int a, int b, boolean[] isPrime) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[10_000];
        int time = 0;
        q.offer(a);
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size; s++){
                int now = q.poll();
//                System.out.println(time+" "+now);
                if(now == b){
                    return time;
                }
                for(int i = 10 ; i < 100_000 ; i*=10){
                    for(int j = 0 ; j < 10 ; j++){
                        int temp = (now / i) * i;
                        if(i >= 100){
                            temp += (now % (i / 10));
                        }
                        temp += j * i/10;
                        if(temp < 10_000 && isPrime[temp] && !visited[temp]){
                            visited[temp] = true;
                            q.offer(temp);
                        }
                    }
                }
            }
            time++;
        }
        return -1;
    }
}