[JAVA/1963번] 소수 경로

---

문제

---

입력 및 출력

---

풀이

import java.io.*;
import java.util.*;
class Node {
    int number; // 소수 숫자
    int count; // 횟수
    public Node(int number, int count) {
        this.number = number;
        this.count = count;
    }
}
public class Main {
    public static boolean[] visit;
    public static int currentPW;
    public static int changePW;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 테스트케이스 T
        int T = Integer.parseInt(br.readLine());

        // 테스트케이스 수 만큼 반복문을 수행
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            currentPW = Integer.parseInt(st.nextToken());
            changePW = Integer.parseInt(st.nextToken());
            visit = new boolean[10000];
            bfs();
        }
    }
    private static void bfs() {
        // Node타입을 갖는 큐 선언
        Queue < Node > queue = new LinkedList < > ();

        // 큐에 현재 비밀번호를 추가
        queue.add(new Node(currentPW, 0));

        // 현재 비밀번호와 변경할 비밀번호가 같을 경우 0을 출력
        if (currentPW == changePW) {
            System.out.println(0);
            return;
        }

        // 큐가 비어있지 않으면 반복문을 수행
        while (!queue.isEmpty()) {
            // 큐의 가장 앞을 꺼낸다.
            Node node = queue.poll();
            if (!visit[node.number]) {
                // 방문처리를 한다.
                visit[node.number] = true;
                char[] numbers = Integer.toString(node.number).toCharArray();

                // 한 자릿수에서 변경할 수 있는 경우의 수 9
                for (int i = 0; i <= 9; i++) {
                    // 숫자 자릿수(1000, 100, 10, 1)
                    for (int j = 0; j < 4; j++) {
                        if (i == 0 && j == 0) {
                            continue;
                        }
                        // 각 자리수에 해당하는 숫자를 꺼낸다.
                        char number = numbers[j];
                        numbers[j] = (char)(i + '0');
                        int n = Integer.parseInt(String.valueOf(numbers));
                        numbers[j] = number;
                        if (visit[n]) {
                            continue;
                        }
                        // Prime메서드를 호출하여 소수일 경우
                        if (Prime(n)) {
                            // 해당 숫자와 변경 할 비밀번호가 같을 경우
                            if (n == changePW) {
                                // 횟수 + 1을 출력
                                System.out.println(node.count + 1);
                                return;
                            }
                            // 그 외의 경우 새로운 노드 추가
                            queue.add(new Node(n, node.count + 1));
                        }
                    }
                }
            }
        }
        System.out.println("Impossible");
    }
    private static boolean Prime(int n) {
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

---

결과 및 해결방법

[결과]

[정리]

해결방법
이전에 풀었던 소수구하기 문제와 BFS 문제를 섞으면 해결할 수 있는 문제였다.

소수를 처리하는 방법은 두 가지로 생각해보았다. 첫 번째는 1000부터 9999까지 모든 소수를 배열에 저장하는 것, 두 번째는 결과로 나온 수가 소수인지 판단하는 것 나는 이 문제를 해결하기 위해 두 번째 방법을 사용하였다.

노드는 소수로 구성된 비밀번호를 저장하는 number변수와 횟수를 나타내는 count변수로 구성되어 있다.

다음으로 소수를 구하는 Prime메소드를 살펴보자! 소수구하기 문제에서 사용했던 방법을 가져와 2부터 n^2까지 반복문을 수행하며 나눈 나머지가 0이 아닌 경우 TRUE값을 반환하는 것을 확인할 수 있다.

다음으로 BFS함수를 확인해보자! 일반적인 BFS문제와 마찬가지로 구성되어 있는 것을 확인할 수 있다.

여기서 핵심은 자릿수 계산이다. 자릿수 계산을 위해 숫자를 쪼개어 하나의 문자로 만들어 주었다. 다음으로 한 자릿수에서 변경할 수 있는 수의 개수인 10개 숫자의 자릿수 4개로 설정하여 이중 반복문으로 구성하였다. 각 자릿수에 해당하는 문자를 꺼내고 해당 자리에 0~9까지 숫자를 넣으며 새로운 소수를 만든다.

해당 소수가 이전에 방문했던 경우 다음 반복문으로 넘어가고 그 외의 경우 소수인지 판단을 하고, 변경할 변수의 값과 동일하면 횟수를 화면에 출력하고 그 외의 경우 새로운 노드 객체를 생성한다.

모든 경우의 수를 한 이후에도 찾을 수 없다면 Impossible을 화면에 출력한다.