[BOJ1963/Java] 소수 경로

1. 문제 요약

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

1963번: 소수 경로

하나의 소수에서 한자리씩 바꿔가면서 다른 소수를 만들어야 한다. 몇 단계를 거쳐야 지금의 소수에서 목표 소수를 만들 수 있을까?

 

2. 입/출력

3. 접근 아이디어

일단 먼저 해야할 일을 정리해야한다.

1. 하나의 소수에서 한자리씩 바꾼다.

2. 바꾼 숫자가 소수인지 아닌지 확인한다.

3. 소수라면 해당 숫자에서 또 다른 숫자로 갈 수 있도록 1, 2번을 반복한다.

-> 그렇다면 이 과정에서

1) 내가 몇 단계에서 해당 소수를 방문했는지 체크할 필요가 있다.

2) 목표 소수까지 최단으로 도착해야하기 때문에 소수 사이를 탐색할 때 BFS를 사용한다.

 

4. 작성 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static boolean[] prime = new boolean[10000];
	
	static void initPrime() {
		for(int i = 2; i<10000; i++) {
			prime[i] = true;
		}
		
		for(int i = 2; i<10000; i++) {
			if(!prime[i]) continue;
			
			for(int j = 2*i; j<10000; j+=i) {
				prime[j] = false;
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		initPrime();
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		while(N-- > 0) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			if(start == end) {
				sb.append(0).append('\n');
				continue;
			}
			
			boolean[] visited = new boolean[10000];
			int[] depth = new int[10000];
			Queue<Integer> queue = new ArrayDeque<>();
			queue.add(start);
			visited[start] = true;
			depth[start] = 0;
			
xx:			while(!queue.isEmpty()) {
				int now = queue.poll();
				for(int i = 0; i<4; i++) {
					int j;
					if(i<3) j = 0;
					else j = 1;
					for(;j<10; j++) {
						int temp = (int) (now - (int)((int)(now/Math.pow(10, i))*Math.pow(10, i)-(int)(now/Math.pow(10, i+1))*Math.pow(10, i+1)) + j*Math.pow(10, i));
						if(prime[temp] && !visited[temp]) {
							if(temp == end) {
								sb.append(depth[now]+1).append('\n');
								break xx;
							}
							queue.add(temp);
							visited[temp] = true;
							depth[temp] = depth[now]+1;
						}
					}
				}
			}
		}	
		System.out.println(sb);
	}

}