[BOJ 1963] 소수 경로 (Java)

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

1963번: 소수 경로

import java.util.*;

public class P1963 {
	static boolean[] prime=new boolean[10000];
	static boolean[] visit;
	static int T;
	static String A, B;
	static Queue<Pair> q;
	public static boolean isPrime(int N) {
		return !prime[N];
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		T=sc.nextInt();
		prime[0]=prime[1]=true;
		for (int i=2; i*i<=9999; i++) {
			if (!prime[i]) {
				for (int j=i*i; j<=9999; j+=i)
					prime[j]=true;
			}
		}
		for (int i=0; i<T; i++) {
			visit=new boolean[10000];
			q=new LinkedList<>();
			A=sc.next();
			B=sc.next();
			boolean isPossible=false;
			q.add(new Pair(A, 0));
			visit[Integer.parseInt(A)]=true;
			while (!q.isEmpty()){
				Pair p=q.poll();
				if (p.s.equals(B)) {
					isPossible=true;
					System.out.println(p.count);
					break;
				}
				for (int d=0; d<4; d++) {
					for (int n=0; n<=9; n++) {
						char[] temp=p.s.toCharArray();
						temp[d]=(char)('0'+n);
						String next=String.valueOf(temp);
						int num=Integer.parseInt(next);
						if (num<1000)
							continue;
						if (!visit[num] && isPrime(num)) {
							visit[num]=true;
							q.add(new Pair(next, p.count+1));
						}
					}
				}
			}
			if (!isPossible) {
				System.out.println("Impossible");
			}
		}
	}
	public static class Pair{
		String s;
		int count;
		public Pair(String s, int count) {
			this.s=s;
			this.count=count;
		}
	}
	
}

BFS 탐색이고, 탐색 조건은 방문하지 않은 숫자+소수이다. 소수 판별 알고리즘은 에라토스테네스의 체를 사용했다.

다른 분들의 코드를 보니, pair class를 따로 두지 않고 distance 배열을 만들어서 해당 숫자의 인덱스에 +1을 추가하는 식으로 하면 횟수를 계산 가능하다.

또한 내 코드는 탐색할 때 String을 이용해서, charArray로 바꾸고, index 값을 수정해주고 다시 String으로 바꾸는 방식을 사용했는데

다른 방법으로는 큐에 Integer 값을 넣어주고 이것을 StringBuilder 형태로 바꾸어서 setCharAt 으로 인덱스에 해당되는 값을 수정가능하다.

StringBuilder sb=new StringBuilder(String.valueOf(num));
sb.setCharAt(index, (char)('0'+v));
return Integer.parseInt(sb.toString());