1. 문제
1963번: 소수 경로
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금
www.acmicpc.net
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
- “이제 슬슬 비번 바꿀 때도 됐잖아”
- “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
- “그럼 8179로 해”
- “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
- “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
- “귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
2. 풀이
InitPrime
static boolean배열에 소수인지 아닌지 판별할 수 있도록 값을 넣었다.
소수이면 false, 소수가 아니라면 true가 저장된다.
static boolean[] prime = new boolean[10000];
private static void initPrime(){
//소수이면 false
prime[0] = prime[1] = true;
for(int i=2;i<10000;i++){
if(prime[i]) continue;
for(int j=i*2;j<10000;j+=i){
prime[j] = true;
}
}
}
BFS
a,b를 받아서 a가 b에 도달하는 데 얼마나 걸리는 지 확인하는 메서드다. 큐를 사용했다.
queue에 먼저 a를 넣고 queue가 빌 때까지 반복한다.
1. 만약 방문한 적 있다면 continue한다.
2. visited[num] = true로 방문처리한다.
3. 만약 현재 노드가 b와 동일하다면 value를 리턴하고 끝낸다. 여기서 value는 a부터 해당 숫자까지 도달하는 데 걸린 최소횟수다.
4. numAr에 한자리수씩 숫자를 넣는다. 나중에 거듭제곱할 때 편하게 하기 위해서 0은 일의 자리, 3은 천의 자리로 했다.
5. 자릿수 하나하나 보면서 그 자리에 다른 숫자를 넣고 탐색한다.
5-1. 천의 자리일 때 j가 0일 수 없다. 숫자는 1000이상이기 때문이다. continue한다.
5-2. 원래의 수와 동일하면 안된다. numAr[i]==j이면 continue한다.
5-3. 새로 계산한 숫자가 소수이고 방문한 적 없다면 큐에 넣는다.
큐가 비었는데도 return되지 않았다면 -1을 리턴한다.
private static int solve(int a, int b){
Queue<int[]> queue = new ArrayDeque<>();
boolean[] visited = new boolean[10000];
queue.offer(new int[]{a,0});
int[] now;
int num;
int[] numAr = new int[4];
while(!queue.isEmpty()){
now = queue.poll();
num = now[0];
if(visited[num]) continue;
visited[num] = true;
if(num==b){
//끝나는 조건
return now[1];
}
//숫자 해체
for(int i=0;i<4;i++) {
numAr[i] = num%10;
num/=10;
}
for(int i=0;i<4;i++){
for(int j=0;j<10;j++){
if(i==3 && j==0) continue;//천의자리는 0이면 안됨
if(numAr[i]==j) continue;//원래 수와 동일하면 안됨
int next = (int) (now[0]-(numAr[i]-j)*Math.pow(10,i));
//소수이고 방문한 적 없어야함
if(!prime[next] && !visited[next]) queue.offer(new int[]{next,now[1]+1});
}
}
}
return -1;
}
Main
1. 먼저 소수배열을 초기화시킨다.
2. 값을 입력받은 후 solve메서드 실행결과를 result에 저장한다.
3. 만약 result가 -1이라면 불가능한 경우이므로 Impossible을 sb(StringBuilder)에 더한다.
4. 3의 경우가 아니라면 result를 sb에 더한다.
5. 마지막으로 sb를 출력한다.
public static void main(String[] args) throws IOException {
initPrime();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
while(T-->0){
st = new StringTokenizer(in.readLine());
int result = solve(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
if(result<0) sb.append("Impossible\n");
else sb.append(result).append('\n');
}
System.out.print(sb);
}
3. 결과
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 1715 카드 정렬하기 - JAVA (0) | 2023.02.09 |
---|---|
[BOJ] 1068 트리 - JAVA (0) | 2023.02.08 |
[BOJ] 13398 연속합2 - JAVA (0) | 2022.12.16 |
[BOJ] 1922 네트워크 연결 - JAVA (0) | 2022.12.16 |
[BOJ] 18111 마인크래프트 - JAVA (0) | 2022.12.16 |
댓글