백준 온라인 저지의 1963번 소수 경로 문제입니다.
[링크] https://www.acmicpc.net/problem/1963
문제 조건과 설명
입력으로 네 자리 소수 a, b가 주어집니다.
이제 소수 a에서 소수 b로 바꿔야 하는데, 바꿀 때의 조건은 다음과 같습니다.
- 숫자 중 한 자리만 바꿔야 한다.
- 바꾼 그 숫자도 소수여야 한다.
예를 들어, 1033을 8179로 바꾸려면 다음과 같은 과정을 거칠 수 있습니다.
1033 - 1733 - 3733 - 3739 - 3779 - 8779 - 8179
이처럼 한 번에 한 자리만 바꿀 수 있고, 바뀌는 과정에서의 모든 숫자들 또한 소수여야 합니다.
이 때 a에서 b로 바꿀 때의 최소 변환 횟수를 구하면 됩니다. 위의 경우 변환 횟수가 6회 입니다.
Input
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
Output
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다.
불가능한 경우 Impossible을 출력한다.
생각한 아이디어
먼저 특정 숫자가 소수임을 판별하기 위해 에라토스테네스의 체를 이용하여 구해 놓습니다.
에라토스테네스의 체로 소수 구하기 : https://chanhuiseok.github.io/posts/algo-42/
이후 BFS를 활용하여 탐색합니다.
- 처음 들어온 숫자의 각 자릿수를 변경해 가면서, 소수인 경우 큐에 push 합니다.
- 단, 이미 push한 숫자는 더 이상 들어갈 수 없도록 visit 배열로 관리합니다.
- 자릿수를 변경해 가면서 판단하는 도중, 최종 목적지인 b와 같을 경우 반복문을 바로 끝냅니다.
- 만약 큐가 빌 때까지 최종 목적지 b와 같았던 적이 한 번도 없을 경우, Impossible 입니다.
사실 디버깅을 하면서, 매 반복문마다 큐에 많은 숫자가 들어가는 것을 확인한 뒤 시간 초과가 나지 않을까 싶었지만… 저지에 제출하고 보니 생각보다 실행시간이 그리 크지 않았습니다.
큐에는 방문하지 않은 소수만 들어갈 수 있기 때문에 생각보다 큰 오버헤드가 아닌 것 같습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring> //memset시 필요
using namespace std;
int seive[10001];
int visit[10001];
int main() {
int T;
scanf("%d", &T);
for (int x = 2; x < 10001; x++) {
if (seive[x] == 0) {
for (int u = 2 * x; u < 10001; u += x) {
seive[u] = 1;
}
}
}
int a, b, result_depth;
for (int i = 0; i < T; i++) {
bool finishFlag = false;
queue<pair<int, int>> q;
memset(visit, 0, sizeof(visit));
scanf("%d %d", &a, &b);
q.push({ a,0 });
if (a == b) {
printf("0\n");
continue;
}
while (!q.empty() && !finishFlag) {
int num = q.front().first;
int depth = q.front().second;
q.pop();
string strNum;
for (int i = 0; i < 4; i++) {
strNum = to_string(num);
for (int j = 0; j <= 9; j++) {
// 숫자를 바꿔보기
strNum[i] = j + 48;
int stoiNum = stoi(strNum);
if (stoiNum < 1000 || stoiNum == a) continue;
if (seive[stoiNum] == 0 && visit[stoiNum] == 0) {
if (stoiNum == b) {
result_depth = depth + 1;
finishFlag = true;
break;
}
q.push({ stoiNum, depth + 1 });
visit[stoiNum] = 1;
}
}
if (finishFlag) break;
}
}
if (finishFlag)
printf("%d\n", result_depth);
else if (!finishFlag)
printf("Impossible\n");
}
return 0;
}