이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 61 번째 글 입니다.
목차
골드5 : bfs 문제이다.
생각
최소 경로를 묻는 문제로써, 완전 탐색으로 풀이할 수 있다. 이 때, 중요한 점은, 한번의 스텝을 넘어감에 있어서 소수여야 한다는 것, 그리고 불가능하다는 것을 알려주기 위한 visited를 만드는 것이다. 재방문 했을 경우, 탐색을 하지 않을 경우 불가능한 것은 모든 경로를 다 검토했을 때, 답이 없는 경우이다.
- 소수인가?
- 방문한 숫자인가?
- 최종 경로인가?
이 세가지 질문을 구현하면 답은 쉽게 나온다.
Code
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <string.h>
using namespace std;
bool isPrime[10000];
bool isVisit[10000];
int T;
void SieveOfEratosThenes(){
memset(isPrime, 1, sizeof(isPrime));
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i*i < 10000; i++) {
if (!isPrime[i]) continue;
for (int j = i*i; j < 10000; j += i) {
isPrime[j] = false;
}
}
}
int BFS(int start, int end){
queue<pair<int, int>> q;
q.push(make_pair(start, 0));
while (!q.empty()) {
pair<int, int> now = q.front();
q.pop();
isVisit[now.first] = true;
if (now.first == end) return now.second;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 10; j++) {
if (i == 0 && j == 0) continue;
string now_s = to_string(now.first);
int nowDepth = now.second;
now_s[i] = char('0' + j);
int candidate = stoi(now_s);
if (!isVisit[candidate] && isPrime[candidate]) {
q.push(make_pair(candidate, nowDepth+1));
}
}
}
}
return -1;
}
int main(){
// cout << char('0' + 7);
cin >> T;
SieveOfEratosThenes();
for (int tc = 0; tc < T; tc++) {
memset(isVisit, 0, sizeof(isVisit));
int a, b;
cin >> a >> b;
int result = BFS(a, b);
if (result == -1) cout << "Impossible" << '\n';
else cout << result << '\n';
}
return 0;
}