[백준 1963] 소수 경로 C++

문제

백준 1963 소수 경로 C++

1963번: 소수 경로

풀이

1. 에라토스테네스의 체를 사용하여 1 ~ 9999까지 소수 판정을 한다.

1-1. 999 이하의 수는 비밀번호로 허용되지 않으므로 소수가 아니라고 설정한다.

2. bfs로 루프를 돌면서 해당 숫자에서 한 자리만 바꾼 수가 소수인 경우만 Queue에 push 해준다.

3. cnt를 따로 체크해주면서, 변환이 가능하면 cnt를 출력하고 불가능하면 Impossible을 출력한다.

 

한 자리만 다른 수 만드는 로직을 string을 통해 훨씬 깔끔하게 만들 수 있었는데,,, 너무 대수적으로 짜서 코드가 난잡해 보인다.

소스 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
 
 
bool visited[10000];
bool isPrime[10000];
int T;
 
int CalDigit(int num, int digit) {
    while (digit--)
    {
        num /= 10;
    }
    return num % 10;
}
int bfs(int start, int target) {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    q.push(make_pair(start, 0));
    visited[start] = true;
    while (!q.empty()) {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (num == target) {
            return cnt;
        }
        int temp = 1;
        // 일의 자리부터 바꿔주기
        for (int i = 0; i < 4; i++) {
            // 해당 자리의 수 구하기
            int digit = CalDigit(num, i);
            int t = num - digit * temp;
            for (int j = 0; j <= 9; j++) {
                int next = t + j * temp;
                if (!visited[next] && isPrime[next]) {
                    q.push(make_pair(next, cnt + 1));
                    visited[next] = true;
                }
            }
            temp *= 10;
        }
    }
    return -1;
}
 
// 에라토스테네스의 체
void SieveofEratosthenes() {
    for (int i = 1; i < 10000; i++) {
        isPrime[i] = true;
    }
    for (int i = 2; i < 100; i++) {
        if (!isPrime[i])
            continue;
        for (int j = i * i; j < 10000; j += i) {
            isPrime[j] = false;
        }
    }
    for (int i = 1; i < 1000; i++) {
        isPrime[i] = false;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    SieveofEratosthenes();
    while (T--) {
        int a, b;
        cin >> a >> b;
        int result = bfs(a, b);
        if (result == -1) {
            cout << "Impossible" << '\n';
        }
        else {
            cout << result << '\n';
        }
    }
    return 0;
}