Life Engineering
[BOJ 1963] 소수 경로 (Java) 본문
https://www.acmicpc.net/problem/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());
'Problem Solving' 카테고리의 다른 글
[BOJ 2661] 좋은 수열 (Java) (0) | 2022.01.18 |
---|---|
[BOJ 17140] 이차원 배열과 연산 (JAVA) (0) | 2022.01.17 |
[BOJ 2589] 보물섬 (JAVA) (0) | 2022.01.04 |
[프로그래머스] 블록 이동하기 (C++) (0) | 2021.12.16 |
[BOJ 17142] 연구소 3 (C++) (0) | 2021.12.15 |