[백준] 1963번 - 소수 경로 [Java]

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

 

[백준] 1963번 - 소수 경로 [Java]

[백준] 1963번 - 소수 경로 [Java]

---

1.  아이디어

 

에라토스테네스의 체를 이용한 소수 판정과 BFS 알고리즘을 조합해서 소수 경로의 길이를 구할 수 있다.

---

2. 문제풀이

 

먼저 에라토스테네스의 체로 1000부터 9999 사이의 소수를 구해서 HashSet에 저장했다.

이후 BFS 알고리즘에서 4자리 소수의 각 자릿수를 바꿔보며 소수이면 Queue에 넣는 방식으로 구현했다.

몫과 나머지 연산을 응용해서 특정 자릿수 변경을 해주면 간단하게 구현할 수 있다.

소수 경로는 BFS 알고리즘의 최단 경로 구하기와 동일하다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        Set<Integer> primes = getPrimes();

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int result = bfs(primes, start, end);

            if (result >= 0) sb.append(result).append("\n");
            else sb.append("Impossible\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static int bfs(Set<Integer> primes, int start, int end) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);

        boolean[] visited = new boolean[10000];
        visited[start] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int item = q.poll();
                if (item == end) return dist;

                for (int j = 0; j < 10; j++) {
                    int num1 = j * 1000 + item % 1000;
                    if (primes.contains(num1) && !visited[num1]) {
                        q.offer(num1);
                        visited[num1] = true;
                    }

                    int num2 = item / 1000 * 1000 + j * 100 + item % 100;
                    if (primes.contains(num2) && !visited[num2]) {
                        q.offer(num2);
                        visited[num2] = true;
                    }

                    int num3 = item / 100 * 100 + j * 10 + item % 10;
                    if (primes.contains(num3) && !visited[num3]) {
                        q.offer(num3);
                        visited[num3] = true;
                    }

                    int num4 = item / 10 * 10 + j;
                    if (primes.contains(num4) && !visited[num4]) {
                        q.offer(num4);
                        visited[num4] = true;
                    }
                }
            }

            dist++;
        }

        return -1;
    }

    private static Set<Integer> getPrimes() {
        boolean[] isPrime = new boolean[10000];
        Arrays.fill(isPrime, true);

        for (int i = 2; i * i < 10000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < 10000; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        Set<Integer> primes = new HashSet<>();
        for (int i = 1000; i < 10000; i++) {
            if (isPrime[i]) primes.add(i);
        }

        return primes;
    }

}

---

4. 후기