[KOITP] 소수 경로

출처 : http://koitp.org/problem/PRIMEPATH/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	876	387 (44%)	321

문제

형석이는 다음날 SDS에 강의를 하러 간다. 하지만 아침에 일찍 일어나야 한다는 부담감에 고급 알람 시계를 준비하였다. 최근에 화장실 사진찍기, 뺨 때리기, 냄새 뿌리기 등의 알람 시계가 나오고 있지만, 형석이는 강의를 위해 머리를 써야 끌 수 있는 알람을 준비하였다.

이 시계의 시간을 맞춰 놓고, 그 시간이 되어 울리기 시작하면, 4자리의 소수 2개가 고급 알람 시계에 표시된다. 첫 번째 적혀 있는 수는 숫자를 변경할 수 있게 되어있다. 그럼 이제 알람을 끄는 방법은 간단하다. 첫 번째 적혀 있는 소수를 두 번째 적혀 있는 소수로 변경하면 된다. 이때, 한번에 한자리만 변경할 수 있고, 한자리를 변경하였을 때, 변경된 수는 소수이어야 한다. 또한 4자리 소수이기 때문에, 경로 중간에도 4자리를 유지해야한다. (즉, 1000이상의 소수) 형석이는 알람이 계속 울리는 것이 싫기 때문에, 최대한 빠르게 알람을 끄고 싶어한다. 형석이를 도와 어떻게 하면 최소한의 단계로 첫 번째 소수를 두 번째 소수로 변경할 수 있는지 구하시오.

예를 들어서 1033이라는 수를 8179로 변경한다면, 1033 1733 3733 3739 3779 8779 8179의 순서로 변경이 가능하다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에 고급 알람 시계에 적혀 있는 두 개의 소수가 공백으로 분리되어 주어진다. (1,000 ≤ 소수 ≤ 9,999)

출력

각 테스트 케이스마다 첫 번째 줄에 첫 번째 소수를 두 번째 소수로 변경하는 최소한의 단계수를 출력한다.

힌트

예제 입력

3
1033 8179
1373 8017
1033 1033

예제 출력

6
7
0

< Comment >

 이전의 문제에 이어서 BFS 문제입니다. 사실 풀었다고 하기에도 조금 찝찝한 기분인데, DFS나 BFS를 잘 익혀두었다면 별 걱정을 안 했을텐데라는 생각도 듭니다. 이론으로만 기억하고 실제 구현을 별로 안 하다보니 늘 헷갈리는 부분이 있는 듯 합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class PrimeAlarm {
	
	public static int T = 0;
	public static boolean isPrime[] = null;
	public static boolean isVisited[] = null;
	
	public static int D[] = null;
	
	public static Queue<Integer> queue = new LinkedList<Integer>();
	
	public static boolean isPrime(int num) {
		
		if (num == 1 || num == 2) {		return true;		}
		
		for (int i = 2 ; i < num ; i++) {
			if (num % i == 0) {		return false;		}
		}
		
		return true;
	}

	public static void BFS (int n) {
		
		isVisited[n] = true;
		queue.add(n);
		
		int curr = 0;
		while (!queue.isEmpty()) {
		
			curr = queue.poll();
			for (int i = 0 ; i < 4 ; i++) {
				
				for (int j = 0 ; j < 10 ; j++) {
					if(i == 3 && j == 0) {
						continue;			// 첫번째 자리는 0이들어가는 것이 불가능하므로
					}
					int num =  (int) Math.pow(10, i);
					int next = curr - ((curr / num) % 10 * num) + j*num;  
					if(isPrime[next] && !isVisited[next]) {
						
						isVisited[next] = true;
						queue.add(next);
						D[next] = D[curr] + 1;
						
					}
				}
			}			
		}
	}
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int start = 0;
		int end = 0;
		
		T = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		
		// 일단 범위 내의 모든 소수를 구하고, BFS, Queue 이용, visited 배열을 만들어 처리
		
		isPrime = new boolean[10000];
		for (int i = 1000 ; i < 10000 ; i++) {
			
			if (isPrime(i)) {
				isPrime[i] = true;
			} else {
				isPrime[i] = false;
			}
		}
		
		for (int tc = 0 ; tc < T ; tc++) {
			
			isVisited = new boolean[10000];
			D = new int[10000];
			
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			
			BFS(start);
			
			bw.write("" + D[end] + "\n");
			bw.flush();
		}
		
		bw.close();
	}
}