BEAKJOON JAVA ALGORITHM #1963(소수경로)

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

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class a1963 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); boolean[] check = new boolean[10001]; for(int i=2; i<=10000; i++) { //에라토스테네스의채 if(check[i] == false) { for(int j=i*i; j<=10000; j+=i) { check[j] = true; } } } for(int j=0; j<=10000; j++) { check[j] = !check[j]; } for(int i=0; i<num; i++) { int a = sc.nextInt(); int b = sc.nextInt(); boolean[] c = new boolean[10001]; int[] d = new int[10001]; c[a] = true; d[a] = 0; Queue<Integer> q = new LinkedList<>(); q.add(a); while(!q.isEmpty()) { int now = q.remove(); for(int j=0; j<4; j++) { for(int k=0; k<=9; k++) { int next = change(now, j, k); if(next != -1) { if(check[next] == true && c[next] == false) { q.add(next); c[next] = true; d[next] = d[now] + 1; } } } } } System.out.println(d[b]); } } public static int change(int now, int i, int j) { if(i == 0 && j == 0) { return -1; } String s = Integer.toString(now); StringBuilder sb = new StringBuilder(s); sb.setCharAt(i, (char)(j+'0')); //숫자 제대로 들어가게할라고 +'0'(아스키코드) return Integer.parseInt(sb.toString()); } }