1963번: 소수 경로
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금
www.acmicpc.net
문제
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
- “이제 슬슬 비번 바꿀 때도 됐잖아”
- “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
- “그럼 8179로 해”
- “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
- “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
- “귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
입력
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
출력
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
예제 입력 1
3
1033 8179
1373 8017
1033 1033
예제 출력 1
6
7
0
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair {
int now;
int time;
Pair(int now, int time) {
this.now = now;
this.time = time;
}
}
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int ans;
static boolean[] check = null;
public static boolean isPrime(int num) {
if(num == 2) return true;
if(num == 0 || num == 1 || num % 2 == 0) return false;
for(int i = 3; i <= Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
public static void bfs(int start, int destination) {
Queue<Pair> que = new ArrayDeque<>();
que.add(new Pair(start, 0));
check[start - 1000] = true;
while(!que.isEmpty()) {
Pair p = que.poll();
int now = p.now;
int time = p.time;
if(now == destination) {
ans = time;
return;
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j <= 9; j++) {
if(i == 3 && j == 0) continue; // 천의자리에는 0이 올 수 없음. 반드시 4자리 수
int digit = (int)Math.pow(10, i);
int temp = now / (int)Math.pow(10, i) % 10; // temp = now의 i번째 자리의 수
int sub = digit * temp;
int sum = digit * j;
int next = now - sub + sum;
if(!check[next - 1000] && isPrime(next)) {
que.add(new Pair(next, time + 1));
check[next - 1000] = true;
}
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while(T-- > 0) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
check = new boolean[9000]; // 0 ~ 8999 == 1000 ~ 9999
bfs(from, to);
System.out.println(ans);
}
}
}
알고리즘 자체는 복잡할 게 없는 전형적인 BFS를 이용한 최단경로 문제였다.
수학 멍청이라서 구현에서 애를 많이 먹었다.
자리수 교체에 String을 사용하지 않고 int로만 처리하고 싶어서 고집을 부렸는데 막상 교체 타겟 자리수의 숫자를 어떻게 뽑아야 할 지 몰라서 애를 먹었다.
결국 뽑아내는법은 구글링을 해서 참고했다.
->
1. 뽑고싶은 자리로 나눈 몫을 구한다.
백의자리의 수를 뽑아야 한다고 할 때, 현재 수를 100으로 나눈 몫을 구하면 그 몫의 1의 자리가 내가 뽑고싶은 백의자리 숫자가 된다.
2. 구한 몫을 10으로 나눈 나머지를 구한다.
그걸 다시 % 10 연산을 사용해 뽑아내면 최초에 타겟한 자리의 수가 나온다.
소수 판별에 대해서는 굳이 '에라토스테네스의 체' 를 사용하지 않아도 시간초과가 발생하지는 않았다.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
| [BOJ] 2251 - 물통 JAVA (0) | 2021.02.12 |
|---|---|
| [BOJ] 9019 - DSLR JAVA (0) | 2021.02.11 |
| [BOJ] 1697 - 숨바꼭질 JAVA (0) | 2021.02.11 |
| [BOJ] 10971 - 외판원 순회 2 JAVA (0) | 2021.02.11 |
| [BOJ] 10819 - 차이를 최대로 JAVA (0) | 2021.02.10 |