[ BOJ ][JAVA][1963] 소수 경로

www.acmicpc.net/problem/1963

1963번: 소수 경로

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	10174	5615	3986	55.531%

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

예제 입력 1

3
1033 8179
1373 8017
1033 1033

예제 출력 1

6
7
0

코드

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

public class p1963 {
    static BufferedReader br;
    static StringTokenizer st;
    static int T;
    static List<Boolean> prime = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        prime.add(false);
        prime.add(false);

        // 에라토스테네스의 체로 미리 소수 세팅
        for (int i = 2; i < 10000; i++) {
            prime.add(true);
        }
        for (int i = 2; i * i < 10000; i++) {
            if (prime.get(i)) {
                for (int j = i * i; j < 10000; j+=i) {
                    prime.set(j, false);
                }
            }
        }

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            bfs(a, b);
        }
    }

    static void bfs(int a, int b) {
        Queue<Integer> q = new LinkedList<>();
        int[] d = new int[10000];
        boolean[] check = new boolean[10000];
        q.add(a);
        check[a] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j <= 9; j++) {
                    if (i == 0 && j == 0) {
                        continue;
                    }
                    int k = change(cur, i, j);
                    if (prime.get(k) && !check[k]) {
                        d[k] = d[cur] + 1;
                        check[k] = true;
                        q.add(k);
                    }
                }
            }
        }

        System.out.println(d[b]);
    }

    // StringBuilder의 setCharAt(인덱스, 바꿀 문자)를 사용하면 수를 바꿔넣을 수 있다.
    static int change(int num, int index, int v) {
        StringBuilder sb = new StringBuilder(String.valueOf(num));
        sb.setCharAt(index, (char)(v + '0'));
        return Integer.parseInt(sb.toString());
    }

}