백준 1693번 - 소수 경로

코드

public class Main {

    static final int LEN = 10000;
    static boolean[] prime = new boolean[LEN];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;

        for (int i = 2; i <= Math.sqrt(LEN); i++) {

            if (!prime[i]) {
                continue;
            }

            for (int j = i*2; j < LEN; j += i) {
                prime[j] = false;
            }
        }

        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            String first = st.nextToken();
            String second = st.nextToken();
            checkChangePrime(first, second);
        }
    }

    private static void checkChangePrime(String first, String second) {

        Set<String> set = new HashSet<>();

        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(first, 0));

        set.add(first);

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

            if (current.getNum().equals(second)) {
                System.out.println(current.getDepth());
                return;
            }

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j <= 9; j++) {
                    if (i == 0 && j == 0) {
                        continue;
                    }

                    StringBuilder sb = new StringBuilder(current.getNum());
                    sb.setCharAt(i, (char) ('0' + j));

                    String next = sb.toString();
                    if (prime[Integer.parseInt(next)] && !set.contains(next)) {
                        queue.offer(new Node(next, current.depth + 1));
                        set.add(next);
                    }
                }
            }

        }

        System.out.println(0);

    }

    static class Node {
        private String num;
        private int depth;

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

        public String getNum() {
            return num;
        }

        public int getDepth() {
            return depth;
        }

        public void setDepth(int depth) {
            this.depth = depth;
        }
    }
}

풀이

😎bfs를 통해 풀 수 있는 방법이다. 풀이는 아래와 같다.

1. 먼저 1000 - 9999까지의 소수를 구한다.
2. 입력 받은 값들에 대하여 bfs를 돌린다. set은 이미 체크 한 값을 다시 계산하지 않기 위해 선언한 것이며 queue는 bfs를 위해 선언하였다.
3. 현재 값이 second(목표 값)이라면 해당 depth값을 출력하고 종료 아니라면 다음 for문 진행
4. 각 자리에 대하여 0-9까지의 값을 대입하여 소수를 판별한다. 만약 소수이면서 방문한적 없던 값이라면 queue에 집어 넣는다.

출처 백준 - 소수 경로