백준 1963 소수 경로(에스테라노스의 체, bfs)

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

1963번: 소수 경로

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 10000;
bool decimal[MAX];
int start_decimal, end_decimal;
bool visited[MAX];
typedef struct
{
    int x, cnt;
} Decimal;

void aesteradoschae()
{
    for (int i = 2; i <= MAX; i++)
    {
        if (decimal[i] == false)
            for (int j = i * i; j <= MAX; j += i)
            {
                decimal[j] = true; //false인건 소수 true인건 소수x
            }
    }
}
int bfs(int x)
{
    queue<Decimal> q;
    q.push({x, 0});
    decimal[x] = true;
    while (!q.empty())
    {
        int curX = q.front().x;
        int curCnt = q.front().cnt;
        q.pop();
        if (curX == end_decimal)
        {
            return curCnt;
        }
        int tmp_thousand = curX % 1000;
        for (int i = 1; i <= 9; i++)
        {
            if (!decimal[tmp_thousand + (i * 1000)])
            {
                decimal[tmp_thousand + (i * 1000)] = true;
                q.push({tmp_thousand + (i * 1000), curCnt + 1});
            }
        }
        int tmp_hundred = (curX % 100) + (curX / 1000 * 1000);
        for (int i = 0; i <= 9; i++)
        {
            if (!decimal[tmp_hundred + (i * 100)]){
                decimal[tmp_hundred + (i * 100)] = true;
                q.push({tmp_hundred + (i * 100), curCnt + 1});
            }
        }
        int tmp_ten = (curX % 10) + (curX / 100 * 100);
        for (int i = 0; i <= 9; i++)
        {
            if (!decimal[tmp_ten + (i * 10)]){
                decimal[tmp_ten + (i * 10)]=true;
                q.push({tmp_ten + (i * 10), curCnt + 1});

            }
        }
        int tmp_one = curX / 10 * 10;
        for (int i = 0; i <= 9; i++)
        {
            if (!decimal[tmp_one + i]){
                decimal[tmp_one + i]=true;
                q.push({tmp_one + i, curCnt + 1});

            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcase;
    cin >> testcase;
    while (testcase--)
    {

        aesteradoschae();

        cin >> start_decimal >> end_decimal;
        // cout<<decimal[start_decimal];
        int ans = bfs(start_decimal);
        if (ans == -1)
            cout << "Impossible"
                 << "\n";
        else
            cout << ans << "\n";

        for (int i = 0; i < MAX; i++)
            decimal[i] = false;
    }
}

사실상 크게 어려울거 없는 문제였다. 조금 더 고민하면 testcase 때마다 에스테라노스의 체 함수를 돌리지 않아도 될 것 같긴한데 그냥 제출했다....

 

요 며칠 노트북이 없어서 알고리즘 문제들을 풀지 못했다.

 

하지만 드디어 어제 엄마가 노트북을 사줬다. 원래 가지고 싶었던 노트북이라 기분은 좋았지만, 너무 가격이 쎄서 뭔가 너무 죄송하기도 하다.

 

돈값하는 개발자가 되기 위해 더 노력해야 겠다는 생각이 든다.