[BaekJoon] 1963 소수 경로 (Java)

1.  문제 링크

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

2.  문제

요약

• 창영이는 게임 아이디 비밀번호를 4자리 '소수'로 정해놓았는데 비밀번호를 변경하려고 합니다.
• 비밀번호는 한 번에 한 자리 밖에 바꾸지 못합니다.
• 현재 비밀번호에서 입력받은 네 자리 소수로 바꾸는데 몇 단계나 필요한지 계산을 해보려고 합니다.
• 입력은 항상 네 자리 소수가 주어지고, 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하며, '네 자리 수'라 하였기에 1000 미만의 비밀번호는 허용되지 않습니다.
• 두 개의 소수 사이의 변환에 필요한 최소 횟수가 얼마인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 수 T가 주어지고 두 번째 줄부터 T줄에 거쳐 각 줄에 1쌍씩 네 자리 소수가 주어집니다.
• 출력: 각 테스트 케이스에 대해 두 소수 사이의 변환에 필요한 최소 횟수를 출력하고 만약 불가능하다면 'Impossible'을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static Reader scanner = new Reader();
	static boolean[] primes;
	static char[] start;
	static int end;
	static final char[] candidate = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	static void input() {
		start = scanner.next().toCharArray();
		end = scanner.nextInt();
	}
	
	static void solution() {
		Queue<Prime> queue = new LinkedList<Prime>();
		queue.add(new Prime(start, 0));
		boolean[] visited = new boolean[10000];
		visited[Integer.parseInt(new String(start))] = true;
		while(!queue.isEmpty()) {
			Prime cur = queue.poll();
			if(Integer.parseInt(new String(cur.num)) == end) {
				sb.append(cur.count).append('\n');
				return;
			}
			for(int cipher = 0; cipher < 4; cipher++) {
				for(int index = 0; index < candidate.length; index++) {
					if(cipher == 0 && index == 0) continue;
					if(cur.num[cipher] == candidate[index]) continue;
					char[] other = cur.num.clone();
					other[cipher] = candidate[index];
					if(!visited[Integer.parseInt(new String(other))] && primes[Integer.parseInt(new String(other))]) {
						visited[Integer.parseInt(new String(other))] = true;
						queue.offer(new Prime(other, cur.count + 1));
					}
				}
			}
		}
		sb.append("Impossible").append('\n');
	}
	
	static void findAllPrimes() {
		primes = new boolean[10000];
		Arrays.fill(primes, true);
		primes[0] = primes[1] = false;
		for(int num = 2; num <= Math.sqrt(9999); num++) {
			if(primes[num]) {
				for(int n = num * num; n <= 9999; n += num) primes[n] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		findAllPrimes();
		int T = scanner.nextInt();
		while(T-- > 0) {
			input();
			solution();
		}
		System.out.println(sb);
	}
	
	static class Prime {
		char[] num;
		int count;
		public Prime(char[] num, int count) {
			this.num = num;
			this.count = count;
		}
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {					
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}