[Algorithm] 백준 1963 - 소수 경로 (JAVA)

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

• 사용 알고리즘 - 에라토스테네스의 체, BFS

1. 네 자릿 수 이므로 소수 판별을 9999까지 해둔다. (에라토스테네스의 체)
2. 입력 값을 bfs에 넣어, 자릿수 별 파싱 및 소수 여부 확인
3. Queue(값 비교)와 Hashmap(횟수 및 중복 제거) 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static boolean[] notPrime = new boolean[10000];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        chkPrime();
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int start;
        int end;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.valueOf(st.nextToken());
            end = Integer.valueOf(st.nextToken());
            sb.append(bfs(start,end)).append("\n");

        }
        System.out.println(sb);
    }

    public static String bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        queue.add(start);
        hashMap.put(start,0);
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            int answer = hashMap.get(tmp);
            if (tmp == end) return answer+"";
            else {
                int[] word = { tmp/1000, (tmp/100)%10, (tmp/10)%10, tmp%10 };
                for (int i = 0; i < word.length; i++) {
                    for (int j = 0; j < 10; j++) {
                        if (i == 0 && j == 0) continue;
                        int pos = word[i];
                        word[i] = j;
                        int next = change(word);
                        word[i] = pos;
                        if (notPrime[next]) continue;
                        if (!hashMap.containsKey(next)) {
                            queue.add(next);
                            hashMap.put(next, answer+1);
                        }
                    }
                }
            }
        }
        return "Impossible";
    }

    static int change(int[] arr) {
        int num = arr[0] * 1000 + arr[1] * 100 + arr[2] * 10 + arr[3];
        return num;
    }

    public static void chkPrime() {
        notPrime[0] = notPrime[1] = true;
        for (int i = 2; i < notPrime.length; i++) {
            if (!notPrime[i]) {
                for (int j = i * i; j < notPrime.length; j += i) {
                    notPrime[j] = true;
                }
            }
        }
    }
}