BOJ - 소수 경로(1963)

골드5 : bfs 문제이다.

생각

최소 경로를 묻는 문제로써, 완전 탐색으로 풀이할 수 있다. 이 때, 중요한 점은, 한번의 스텝을 넘어감에 있어서 소수여야 한다는 것, 그리고 불가능하다는 것을 알려주기 위한 visited를 만드는 것이다. 재방문 했을 경우, 탐색을 하지 않을 경우 불가능한 것은 모든 경로를 다 검토했을 때, 답이 없는 경우이다.

1. 소수인가?
2. 방문한 숫자인가?
3. 최종 경로인가?

이 세가지 질문을 구현하면 답은 쉽게 나온다.

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;
}
 

Reference

• 백준(1963번) - 소수 경로