[1963] 소수 경로

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

Key Point

먼저, 에라토스테네스의 체를 이용해 4자리 소수를 구한다.
그리고 한자리씩 바꾸면서 바뀐 수가 소수인지 확인하면 된다.
정점의 개수 10000개 이하

Explain

N을 M으로 바꾸는 최소 변환 횟수를 구하는 문제이므로 BFS
한번에 N에서 한자리만 바꿀 수 있고 바꾼 숫자도 소수여야 한다.
i번째 자리수를 j로 바꾼다. [change]
next = -1 -> 바꿀 수 없음을 의미하며, 첫번째 자리가 0인 경우를 뜻한다.

Code

public class Exam1963 {
	
	public static int change(int num, int index, int digit) {
		if(index == 0 && digit == 0) { // indext와 digit이 0이면 첫번째 자리수가 0을 뜻함
			return -1;
		}
		String s = Integer.toString(num);
		StringBuilder sb = new StringBuilder(s);
		sb.setCharAt(index, (char)(digit+'0'));
		// index번째 자리를 digit으로 바꾼다. 
		return Integer.parseInt(sb.toString());
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[] prime = new boolean[10001];
		
		// 에라토스테네스의 체를 이용한 소수 구하기
		for(int i=2;i<=10000;i++) {
			if(prime[i] == false) {
				for(int j=i*i;j<=10000;j+=i) {
					prime[j] = true;
				}
			}
		}
		
		for(int i=0;i<=10000;i++) {
			prime[i] = !prime[i];
		}
		// prime[] 배열에 true로 check되어 있는 것들이 소수임!
		
		int test_case = sc.nextInt();
		while(test_case-- >0) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			boolean[] check = new boolean[10001];
			int[] dist = new int[10001];
			dist[n] = 0;
			check[n] = true; // 소수임을 의미
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(n);
			while(!q.isEmpty()) {
				int now_location = q.poll();
				for(int i=0;i<4;i++) {
					for(int j=0;j<=9;j++) {
						int next_location = change(now_location,i,j);
						if(next_location != -1) {
							if(prime[next_location] == true && check[next_location] == false) {
								// next_location이 prime[] 배열에서 소수로 체크되어있는지와 check[] 배열에는 false로 체크되어있는지
								// 조건을 확인한다. 
								// 조건에 맞으면 [prime 배열에 존재하면 ] 소수임을 뜻한다. 
								q.add(next_location);
								dist[next_location] = dist[now_location]+1;
								check[next_location] = true; // 소수로 check해버린다.
							} 
						}
					}
				}
			}
			System.out.println(dist[m]);
		}
	}

}