[백준 1963] 소수 경로

 

최소 회수를 출력하라길래 BFS로 풀었다.

 

1. 4자리수의 소수 배열을 저장해 놓는다.

2. 매 탐색시 각 자리수를 0~9로 바꾸며 소수인지 아닌지 체크하며 소수이면 큐에 담는다.

3. 만들어진 수와 입력받은 수가 같으면 정지한다.

 

4자리수가 안되는 수는 모두 소수가 아니라고 저장하여 예외처리했다.

그리고 따로 방문이력을 담은 배열을 만들어 체크해 주어야 불가능한 경우를 알아낼 수 있다.

 

 

public class Main {
    
    static boolean prime[] = new boolean[10000];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        for(int i=2; i<10000; i++)
            for(int j=2; i*j<10000; j++)
                prime[i*j] = true;
        
        for(int i=0; i<1000; i++)
            prime[i] = true;
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        
        while(t-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bfs(a, b);
        }
    }
    
    public static void bfs(int s, int e) {
        Queue<Integer> q = new LinkedList<Integer>();
        boolean visited[] = new boolean[10000];
        q.offer(s);
        
        int cnt = 0;
        boolean success = false;
        while(!q.isEmpty()) {
            int size = q.size();
            
            while(size-->0) {
                int pop = q.poll();
                visited[pop] = true;
                if(pop == e) {
                    success = true;
                    break;
                }
                
                for(int i=1; i<=4; i++) {
                    for(int j=0; j<=9; j++) {
                        int temp = convertNumber(pop, i, j);
                        if(primeCheck(temp) && !visited[temp])
                            q.offer(temp);
                    }
                }
            }
            if(success) break;
            else cnt++;
        }
        System.out.println(success == true ? cnt : "Impossible");
    }
    
    public static int convertNumber(int pop, int i, int j) {
        String temp = String.valueOf(pop);
        String prefix = temp.substring(0, i-1);
        String suffix = temp.substring(i, 4);
        return Integer.parseInt(prefix + j + suffix);
    }
    
    public static boolean primeCheck(int pop) {
        if(!prime[pop]) return true;
        else return false;
    }
}