백준 1963. 소수 경로 :: 돼지개발자

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

"소수를 구하고 BFS를 돌리며 자리수를 잘 체크"

먼저 BFS 탐색 전에 10000 이하의 수의 소수 여부를 저장하고 있는 boolean[] nonPrime 배열을 셋팅한다. 그 후에 BFS 탐색을 통해 목적지에 도착하는지 체크한다. 가능 / 불가능 여부는 boolean형 ok 변수를 통해 체크했다. BFS 탐색중 int origin 변수를 써서 변경한 값을 원래로 되돌려야함을 주의한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int T;
    static boolean[] nonPrime = new boolean[10000];
    static boolean[] visited;
    static Queue<Integer> q = new LinkedList<>();
    static int a,b;
    static int min;
    static boolean ok;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        
        // 소수를 미리 구한다.
        for (int i = 2; i < 10000; i++) {
            for (int j = 2; j < i/2; j++) {
                if(i % j == 0) 
                    nonPrime[i] = true;
            }
        }
        
        while(T-- >0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            
            // 초기화
            visited = new boolean[10000];
            ok = false;
            min = 0;
            q.clear();
            
            // BFS 탐색 시작
            visited[a] = true;
            q.add(a);
            
            loop : while(!q.isEmpty()) {
                int size = q.size();
                for (int s = 0; s < size; s++) {
                    int cur = q.poll();
                    
                    if(cur == b) {
                        ok = true;
                        break loop;
                    }
                    
                    // 현재 4자리 비밀번호를 각 자리수로 분리하여 배열에 저장.
                    int[] digit = {cur/1000 ,(cur%1000) / 100, (cur%100) / 10, cur%10 };
                    
                    for (int i = 0; i < 4; i++) {
                        for (int j = (i== 0 ? 1 : 0); j < 10; j++) {
                            int origin = digit[i];    // 이전 값 저장
                            digit[i] = j;
                            int num = (digit[0]*1000) + (digit[1]*100) + (digit[2]*10) + (digit[3]);
                            digit[i] = origin;    // num만 만들고, 다음 변경을 위해 초기 cur의 배열 상태로 되돌린다.
                            if(visited[num] || nonPrime[num])
                                continue;
                            visited[num] = true;
                            q.add(num);
                        }
                    }
                }
                min++;
            }
            System.out.println(ok ?min : "Impossible");
        }
    }
}