[백준] 1963 소수 경로

문제링크 : www.acmicpc.net/problem/1963

1963번: 소수 경로

 4자리 수 이므로 모든 경우의 수를 탐색하면 되는 문제이다.

어떤 4자리 수에서 숫자 하나를 바꾸어 다른 숫자로 만드는 경우는 4*9이고 이 중에서 소수일 경우만 다음 숫자가 가능하다. 이를 bfs로 구현하면 숫자를 변경한 횟수를 쉽게 알 수 있어서 bfs로 구현 했으며, 소수를 미리 isPrime에 체크했다.

import java.io.*;
import java.util.*;
public class Main {
	public static int[] isPrime;
	public static void init(){
	    for(int i=2;i<10000;i++) {
	        isPrime[i] = 1;
	    }
	    
	    for(int i=2;i<10000;i++) {
	        if(isPrime[i]==0) continue;
	        for(int j=2*i;j<10000; j+=i) {
	            isPrime[j] = 0;
	        }
	    }
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		isPrime = new int[10000];
		init();
		
		for(int i=0;i<n;i++){
			boolean visited[] = new boolean[10000];
			StringTokenizer st = new StringTokenizer(br.readLine());
			String origin = st.nextToken();
			String wanted = st.nextToken();
			Queue<String> q = new LinkedList<String>();
			q.add(origin);
			visited[Integer.parseInt(origin)] = true;
			int ret = 0;
			boolean suc = false;
			exit:while(!q.isEmpty()){
				int qSize = q.size();
				for(int j=0;j<qSize;j++){
					String cur = q.poll();
					if(cur.equals(wanted)){
						suc = true;
						break exit;
					}
					for(int k=0;k<4;k++){
						for(int l=0;l<10;l++){
							StringBuilder next = new StringBuilder(cur);
							next.setCharAt(k,(char)(l+'0') );
							int rNext = Integer.parseInt(next.toString());
							if(rNext/1000 ==0 || visited[rNext] || isPrime[rNext]==0) continue;
							visited[rNext] = true;
							q.add(next.toString());
						}
					}
				}
				ret++;
			}
			if(suc){
				System.out.println(ret);				
			}else{
				System.out.println("Impossible");
			}
		}
	}

}