[백준] 1963번 : 소수 경로 - JAVA [자바]

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

bfs 알고리즘 문제이다.

1. 4자리 수 A를 제일 앞의 자리 수부터 마지막 자리의 수까지 0부터 9까지 변경하여 수를 만든다.
2. 만들어진 수가 소수인지 혹은 이미 만들어진 수인지 확인한다.
3. 소수이며 아직 만들어지지 않은 수이면 그 전의 숫자를 만들기 위해 변경한 횟수 + 1을 하여 큐에 삽입한다.
4. 큐를 탐색하며 목표한 B가 되면 횟수를 비교하여 가장 최소값을 출력한다.

소수 구하기 : 에라토스테네스의 체를 이용하여 4자리 수이므로 10,000 이하의 소수를 모두 구한다.

		static boolean[] prime = new boolean[10000]
        // 소수는 false
        // 0 과 1은 소수가 아니므로 제외
        prime[0] = prime[1] = true; // 소수 아님

        for (int i = 2; i * i < prime.length; i++) {
            if (prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }

public class bj1963 {
    static boolean[] prime = new boolean[10000], visited;
    static boolean yesAnswer;
    static String ANSWER = "Impossible", A, B;
    static Queue<num> queue = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 소수는 false
        // 0 과 1은 소수가 아니므로 제외
        prime[0] = prime[1] = true; // 소수 아님

        for (int i = 2; i * i < prime.length; i++) {
            if (prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
        	// 다른 테스트이면 답을 구했는지 초기화
            yesAnswer = false;
            // 만들어진 수 즉, 방문 배열도 초기화
            visited = new boolean[10000];
            
            String line = br.readLine();
            String[] split = line.split(" ");
            A = split[0];
            B = split[1];

            bfs(new num(A, 0), new num(B, 0));

            bw.write(ANSWER + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(num A, num B) {
        queue.add(A);

        while (!queue.isEmpty()) {
            num current = queue.poll();

			// 목표한 B가 되면
            if (current.num.equals(B.num)) {
            	// 처음으로 구한 답이면 "Impossible"를 일단 횟수로 변경
                if (!yesAnswer) {
                    ANSWER = String.valueOf(current.count);
                    yesAnswer = true;
                } // 처음으로 구한게 아니면 최소값 비교
                else {
                    ANSWER = String.valueOf(Math.min(Integer.parseInt(ANSWER), current.count));
                }
            }

            char[] charArray = current.num.toCharArray();
            for (int i = 0; i < 4; i++) {
                int number = charArray[i] - '0';
                // 항상 네 자리 수를 유지하기 위해 (제일 앞에 0은 안됨)
                for (int j = (i == 0) ? 1 : 0; j < 10; j++) {
                    // 같은 숫자는 바꾸는 것이 아니므로 패스
                    if (j == number) continue;
                    
                    // i 번째 자리의 수를 j로 변경
                    char changeNum = Character.forDigit(j, 10);
                    StringBuilder sb = new StringBuilder(current.num);
                    sb.setCharAt(i, changeNum);
                    String string = sb.toString();
                    int newNumber = Integer.parseInt(string);
                    
                    // 바꾼 숫자가 소수인지 확인
                    if (!prime[newNumber]) {
                        // 이미 만들어진 숫자인지 확인
                        if (!visited[newNumber]) {
                            visited[newNumber] = true;
                            queue.add(new num(String.valueOf(newNumber), current.count + 1));
                        }
                    }
                }
            }
        }
    }

    public static class num {
        String num;
        int count;

        public num(String num, int count) {
            this.num = num;
            this.count = count;
        }
    }
}