[C/C++] 백준 #1963 소수 경로(너비 우선 탐색)

이번 문제는 소수중 한자리의 숫자만 다른 소수 경로를 찾는 문제입니다.

 

소수를 찾기 위해서 에라토스테네스의 체를 이용해도 되겠지만, 저는 미리 구한 4자리 소수 집합을 사용했습니다.  약간 편법일 수 있겠지만.

 

소수의 경로를 찾기 위해서 소수 후보를 찾는 것이 가장 힘듭니다.  일단 4자리 소수는 모두 홀수 소수이므로 갈 수 있는 경로는 31가지가 됩니다.  그것을 생각해서 한자리 숫자들을 바꾸면서 소수면 너비우선탐색 알고리즘으로 방문을 합니다.  그래서 목표하는 소수가 나오면 그때의 경로횟수가 답이 됩니다.  그런데, 모든 갈 수 있는 경로를 다 갔는데, 목표하는 소수가 나오지 않은 경우(queue가 비어있는 경우)에는 불가능하다고 출력을 내면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1963 - Prime number path
//        - by Aubrey Choi
//        - created at 2019-06-16
//------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include <queue>

const unsigned long oddprimes[] =
{
    0x64b4cb6e, 0x816d129a, 0x864a4c32, 0x2196820d, 0x5a0434c9, 0xa4896120, 0x29861144, 0x4a2882d1,
    0x32424030, 0x08349921, 0x4225064b, 0x148a4884, 0x6c304205, 0x0b40b408, 0x125108a0, 0x65048928,
    0x804c3098, 0x80124496, 0x41124221, 0xc02104c9, 0x00982d32, 0x08044900, 0x82689681, 0x220825b0,
    0x40a28948, 0x90042659, 0x30434006, 0x69009244, 0x08088210, 0x12410da4, 0x2400c060, 0x086122d2,
    0x821b0484, 0x0110d301, 0xc044a002, 0x14916022, 0x04a6400c, 0x092094d2, 0x00522094, 0x4ca21008,
    0x51018200, 0xa48b0810, 0x44309a25, 0x034c1081, 0x80522502, 0x20844908, 0x18003250, 0x241140a2,
    0x01840128, 0x0a41a001, 0x36004512, 0x29260008, 0xc0618283, 0x10100480, 0x4822006d, 0xc20c2658,
    0x24894810, 0x45205820, 0x19002488, 0x10c02502, 0x01140868, 0x802832ca, 0x264b0400, 0x60901300,
    0xd0258082, 0x32100100, 0x2186430c, 0x43080011, 0x10480424, 0x0092900c, 0x002d2043, 0x24880906,
    0x0932c040, 0x53008209, 0x96800880, 0x40008141, 0x08481048, 0x20584896, 0x2080c329, 0x92609402,
    0x22812000, 0x05a01044, 0x49019040, 0x000a0420, 0x48348924, 0xc02c8013, 0x24002982, 0x08000845,
    0x52043698, 0x04d00484, 0x44908a00, 0x18653282, 0x020a0090, 0x28024001, 0x9204a440, 0x86110430,
    0x2c004208, 0xc9080452, 0x12486084, 0x44249909, 0x03002400, 0x10002114, 0x05321a01, 0x40402088,
    0x84c30906, 0x60300140, 0x11680218, 0xa2020c90, 0x29860004, 0x82241489, 0x80084102, 0x08801904,
    0x42681210, 0x020004a4, 0x0c061061, 0x12010010, 0x94032010, 0x65124221, 0x0a0c9418, 0x14012804,
    0x40a40a29, 0x014000d0, 0x20410490, 0x4882402d, 0x100020c1, 0x24080130, 0x24845904, 0x82290200,
    0x02586100, 0x48168148, 0x11210010, 0xa0ca0006, 0x04000240, 0x4200b091, 0x06810c04, 0x25144809,
    0x11252092, 0x860a00a0, 0x4802c10c, 0x08452000, 0x06980032, 0x00221304, 0x81480482, 0x12824414,
    0x40101824, 0xd0288043, 0x24812004, 0x2c00d864, 0x41081209, 0x020000a2, 0x4120ca41, 0x180110c0,
    0xa41804a4, 0x20941220, 0x0240a083, 0x04804432, 0x0c001800, 0x8a608640, 0x12886400, 0x00820105,
    0xc101a24a, 0x04096110, 0x60008801, 0x0840b401, 0x80030106, 0x04944008, 0x8029208a, 0x02520c02,
    0x00844201, 0x02648480, 0x30004832, 0x21224044, 0xc3080200, 0x20d004a0, 0x40161840, 0x52280040,
    0x14820890, 0x08101801, 0x0a408209, 0x809320a0, 0x2000c008, 0x01050052, 0x06114010, 0x0000820c,
    0x9a44904b, 0x90802800, 0x09064a04, 0x00280243, 0x00180134, 0x44800965, 0x02240003, 0x14486182,
    0x28120041, 0x51083400, 0x90120504, 0x60848928, 0x10491012, 0x82494026, 0x01109100, 0x8840240a,
    0x04104c10, 0x2ca25000, 0x0a489040, 0x125001b0, 0x04a40008, 0x9228a009, 0x10430002, 0x41200221,
    0x08003281, 0x00520c04, 0x20844921, 0x81010210, 0x22404810, 0x69840101, 0xc80130c1, 0x00884402,
    0x2d02010c, 0x006112c0, 0x30c000a0, 0x08120140, 0x8000200b, 0x84014094, 0x00320040, 0x0b008410,
    0x06010024, 0x41848a29, 0x08081080, 0x80034c94, 0x40964001, 0x50202041, 0xa2892522, 0x20a44040,
    0x01288602, 0x104a2120, 0x08140008, 0x42250440, 0x10432102, 0x21009204, 0x184ca011, 0x84030922,
    0x04108941, 0x01242282, 0x84080814, 0x0900c108, 0x8a41b042, 0x36800002, 0x24a04904, 0x02000091,
    0x02924194, 0x08060801, 0xd0010009, 0x80892816, 0x68000060, 0x500c9001, 0x80400120, 0x41304240,
    0x81252000, 0x00494006, 0x49120108, 0x1820a000, 0xa6010530, 0x28241000, 0xc8200200, 0x12880020,
    0x0092900c, 0x42012602, 0x04004916, 0x01024224, 0x1a0c8088, 0x00100880, 0x44940260, 0x11690088,
    0xa0120830, 0x00841324, 0xc0650082, 0x30002810, 0x01200304, 0xc8010611, 0x20c20080, 0x0c821008,
    0x520c0213, 0xb0004006, 0x01104061, 0x10048698, 0x14920884, 0x41804160, 0x8104101a, 0x20414022,
    0x41005229, 0x10603408, 0x10012800, 0x08840040, 0x48209042, 0x02520404, 0x04200800, 0x000d8200,
    0x10024082, 0x40204805, 0x01000099, 0x00c02406, 0x21048268, 0x08441012, 0xa6400004, 0x0916d020,
    0x024124c9, 0x92090c20, 0x00001240, 0x43090040, 0x02982084, 0x00241101, 0x03002443, 0x30410890,
    0x4c205824, 0x10088280, 0x06812524, 0x20100941, 0x80441018, 0x244a0010, 0x2894010d, 0xc0003080,
    0x84106002, 0x0900020c, 0x08018202, 0x20c20410, 0x04060968, 0x11000018, 0x100b0890, 0x0c028221
};

bool isoddprime(int p)
{
    return (oddprimes[p / 64] & (1 << ((p % 64) / 2))) != 0;
}

int main()
{
    int T;
    static char visited[10000];
    scanf("%d", &T);
    while(T--)
    {
        int from, to;
        std::queue<int> queue;
        scanf("%d%d", &from, &to);
        memset(visited, 0, sizeof(visited));
        queue.push(from);
        visited[from] = 1;
        while(!queue.empty())
        {
            int s = queue.front();
            int d = s / 10000;
            s %= 10000;
            if(s == to)
            {
                printf("%d\n", d);
                break;
            }
            queue.pop();
            for(int i = 1; i < 10; i+=2)
            {
                int t = (s / 10) * 10 + i;
                if(isoddprime(t) && visited[t] == 0)
                {
                    visited[t] = 1;
                    queue.push(t + d * 10000 + 10000);
                }
            }
            for(int i = 0; i < 10; i++)
            {
                int t = (s / 100) * 100 + i * 10 + s % 10;
                if(isoddprime(t) && visited[t] == 0)
                {
                    visited[t] = 1;
                    queue.push(t + d * 10000 + 10000);
                }
            }
            for(int i = 0; i < 10; i++)
            {
                int t = (s / 1000) * 1000 + i * 100 + s % 100;
                if(isoddprime(t) && visited[t] == 0)
                {
                    visited[t] = 1;
                    queue.push(t + d * 10000 + 10000);
                }
            }
            for(int i = 1; i < 10; i++)
            {
                int t = i * 1000 + s % 1000;
                if(isoddprime(t) && visited[t] == 0)
                {
                    visited[t] = 1;
                    queue.push(t + d * 10000 + 10000);
                }
            }
        }
        if(queue.empty()) puts("Impossible");
    }
    return 0;
}

The sieve of Eratosthenes