<Algorithm> 19. 1963번 소수경로

1. 1963번 소수경로 

• 간선의 가중치가 1이고 최소경로를 구하는 문제는 BFS로 접근한다.

• 큐와 DISTANCE가 가장 중요하다. DISTANCE는 경로마다 부여하는 것이 특징

• 예외 사항에 대한 처리가 반드시 필요( ex) 1000보다 작은 수는 처리하지 않음 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Object> res = new ArrayList<>();
        
        for(int T=0; T<N; T++) {
            
            int[] dist = new int[10000];
            boolean[] visited = new boolean[10000];
            boolean flag = false;
            
            st = new StringTokenizer(br.readLine());
            String prev = st.nextToken();
            String chan = st.nextToken();
            
            if(prev.equals(chan)) {
                res.add(0);
                continue;
            }
            
            Queue<String> queue = new LinkedList<>();
             queue.add(prev);
             dist[Integer.parseInt(prev)] = 0;
             visited[Integer.parseInt(prev)] = true;
             
        while(!queue.isEmpty()) {
            
            String input=queue.remove();
            
            for(int i = 0; i < 4 ; i++) {    // 4자리가 한자리씩 바뀌는 경우의 수            
                for(int j = 0; j < 10; j++) {
                    if(!input.substring(i, i + 1).equals(j + "")) { // 기존의 숫자가 같지 않을 때만 실행
                        String temp = input.substring(0,i) + j + input.substring(i+1,4);
                        // 한자리씩 바꾸기
                        
                        int prsInt = Integer.parseInt(temp);
                        
                        if(prsInt <= 1000) continue; // 1000보다 작은 경우는 없음
                        
                        if(!visited[prsInt]) {
                            visited[prsInt] = true;
                            
                            if(primeCheck(temp)) {                                    
                                queue.add(temp); 
                                // 소수일 경우 큐에 저장
                                dist[prsInt] = dist[Integer.parseInt(input)] + 1;
                                // 부모의 distance에 + 1
                                
                                if(temp.equals(chan)) { // 찾았을때
                                    res.add(dist[prsInt]);
                                    flag = true;
                                    queue.clear();
                                    break;
                                }
                            }
                        }
                    }
                } // for j
                if(flag) break;
             }// for i
           }// while
        
        
        
         if(!flag) {
            res.add("Impossible");
         }
      }
        
        for(int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
                
    }
    
    public static boolean primeCheck(String temp) {
        int input = Integer.parseInt(temp);
        int sqrt = (int)Math.round(Math.sqrt(input));
        for(int i=2; i<=sqrt; i++) {
            if(input % i == 0) {
                return false;
            }
        }
        return true;
    }
    
}