1963번 소수 경로

문제를 보고,

바로 2가지를 떠올렸다.

1. 소수 확인

2. BFS 활용

그러나, 숫자 중에서 단 '한 자리 숫자'만 바꾸는 것을 알고 있었으나, 이상하게 잘 안 풀려서, 다른 분의 코드를 참고하였다.

더 열심히 공부해야겠다.

참고로 문제 조건에서

1033 1733 3733 3739 3779 8779 8179

위의 예시가 있었는데, 잘 보면 숫자가 큰 소수에서 작은 소수로 가는 경우도 있다.

나는 이 경우를 생각하지 못 하였다. 무조건 증가하는 소수로 생각했었다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
bool prime[10000] = { false, };
bool num[10000] = { false, };
 
void getPrime()
{
    for (int i = 2; i <= 9999; i++)
    {
        if (num[i]) continue;
 
        prime[i] = true; // 소수 O
 
        for (int j = 2 * i; j <= 9999; j += i)
        {
            num[j] = true; // 소수 X
        }
    }
 
    for (int i = 0; i <= 999; i++)
    {
        prime[i] = false;
    }
}
 
int BFS(int s, int e)
{
    queue<int> q;
 
    bool visit[10000] = { false, };
 
    q.push(s);
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (here == e) return ret;
 
            for (int i = 0; i <= 9; i++)
            {
                int thousand = here / 1000;
                int hundred = (here % 1000) / 100;
                int ten = (here % 100) / 10;
                int one = here % 10;
 
                if (i != thousand && i != 0)
                {
                    int next = here - (thousand * 1000) + i * 1000;
 
                    if (!visit[next] && prime[next]) // 방문하지 않았고, 소수라면 
                    {
                        visit[next] = true;
                        q.push(next);
                    }
                }
 
                if (i != hundred)
                {
                    int next = here - (hundred * 100) + i * 100;
 
                    if (!visit[next] && prime[next])
                    {
                        visit[next] = true;
                        q.push(next);
                    }
                }
 
                if (i != ten)
                {
                    int next = here - (ten * 10) + i * 10;
 
                    if (!visit[next] && prime[next])
                    {
                        visit[next] = true;
 
                        q.push(next);
                    }
                }
 
                if (i != one)
                {
                    int next = here - one + i;
 
                    if (!visit[next] && prime[next])
                    {
                        visit[next] = true;
 
                        q.push(next);
                    }
                }
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    int T = 0, s = 0, e = 0;
 
    getPrime();
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        scanf("%d %d", &s, &e);
 
        int ans = BFS(s, e);
 
        if (ans == -1) printf("Impossible\n");
        else printf("%d\n", ans);
    }
 
    return 0;
}