[백준 1963] 소수 경로

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 본 문제는 2006 NWERC G번 문제로 비밀번호를 4자리 소수로 한다. 만약 비밀번호를 변경하려고 하면 다음과 같은 과정이 필요하다.

1. 비밀번호는 반드시 4자리 소수
2. 비밀번호는 한 번에 한 자리 밖에 못 바꾼다.
3. 예) 현재 비밀번호가 1033일 때 8179로 변경하려면
   • 1033 1733 3733 3739 8779 8179의 과정이 필요하다.

문제 해결 과정은 다음과 같다.

1. 비밀번호 4자리 중 천의 자리부터 0 ~ 9의 숫자로 한 번 바꾼다.
2. 바꾼 숫자가 4자리 소수, 그리고 이전에 바꾼 비밀번호인지 확인한다.
3. 2번 과정이 맞다면 방법을 1 증가한다.
4. 비밀번호를 변경하는데 최소 회수를 출력해야 하므로 BFS로 구현하였다.

< 1. 에라토스테네스의 체 사용>

#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
bool chk[10000];
bool prime[10000];
 
bool is_right(int x) {
    if (x > 1000 && x < 10000) return true;
    else return false;
}
 
int main() {
    int t;
    scanf("%d", &t);
    for (int i = 2; i <= 9999; i++) {
        if (!prime[i]) {
            for (int j = i*i; j <= 9999; j += i) {
                prime[j] = true;
            }
        }
    }
    while (t--) {
        int start, end;
        scanf("%d %d", &start, &end);
        queue<pair<int, int>> q;
        memset(chk, false, sizeof(chk));
        chk[start] = true;
        q.push(make_pair(start, 0));
        int ans = 0;
        while (!q.empty()) {
            int now = q.front().first;
            int cnt = q.front().second;
            q.pop();
            if (now == end) ans = cnt;
            for (int i = 0; i < 4; i++) {
                string tmp = to_string(now);
                for (int j = 0; j <= 9; j++) {
                    tmp[i] = j + '0';
                    int next = stoi(tmp);
                    if (is_right(next) && !prime[next] && !chk[next]) {
                        chk[next] = true;
                        q.push(make_pair(next, cnt+1));
                    }
                }
            }
        }
        if (chk[end]) printf("%d\n", ans);
        else printf("Impossible\n");
    }
}

#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
bool chk[10000];
 
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i*i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
 
bool is_right(int x) {
    if (x > 1000 && x < 10000) return true;
    else return false;
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int start, end;
        scanf("%d %d", &start, &end);
        queue<pair<int, int>> q;
        memset(chk, false, sizeof(chk));
        chk[start] = true;
        q.push(make_pair(start, 0));
        int ans = 0;
        while (!q.empty()) {
            int now = q.front().first;
            int cnt = q.front().second;
            q.pop();
            if (now == end) ans = cnt;
            for (int i = 0; i < 4; i++) {
                string tmp = to_string(now);
                for (int j = 0; j <= 9; j++) {
                    tmp[i] = j + '0';
                    int next = stoi(tmp);
                    if (is_right(next) && is_prime(next) && !chk[next]) {
                        chk[next] = true;
                        q.push(make_pair(next, cnt+1));
                    }
                }
            }
        }
        if (chk[end]) printf("%d\n", ans);
        else printf("Impossible\n");
    }
}