백준 1963 소수 경로

BFS 문제중에 좀 특이하게 맵 탐색이 아닌 다른 공간을 탐색하는 문제이다. 어떤 4자리 소수에서 각 자리수를 바꿔가며 다른 소수로 이동하면서 탐색을 하게 된다.

 

따라서 일단 소수를 찾아놓고, 각 자리수를 바꾼 숫자가 소수인지 확인해야 한다.

소수를 찾아놓을 땐, 에라토스테네스의 체를 이용해 정해진 범위(10000)까지의 소수를 찾는다.

memset(filter, 1, sizeof(filter));

filter[0] = 0;
filter[1] = 0;
for (int i = 2; i < 10000; i++)
{
    if (filter[i])
    {
        for (int j = 2*i; j < 10000; j+=i)
            filter[j] = 0;
    }
}

 

그리고, 탐색을 하는 과정에서 각 자리수를 바꿔야 하므로 조금 더 편하게 이 과정을 하기 위해 현재 상태 숫자를 나타내는 구조체를 만들어 둔다. 구조체에는 숫자가 4개의 배열로 각 자리수를 가진다. 시작점에서 현재까지 몇번 바뀌었는지를 세는 변수 count와, 연산을 편하게 하기 위해 숫자를 리턴하는 함수, 각 자리수에 대한 접근을 하기 위해 operator[]도 작성했다.

struct number{
    int num[4];
    int count;
    int getNumber(){
        return this->num[0] * 1000 + this->num[1] * 100 + this->num[2] * 10 + this->num[3];
    }
    int& operator[](int idx){
        return num[idx];
    }
    number(int input, int count){
        this->num[3] = input % 10; input /= 10;
        this->num[2] = input % 10; input /= 10;
        this->num[1] = input % 10; input /= 10;
        this->num[0] = input % 10; input /= 10;
        this->count = count;
    }
    number() {}
};

 

BFS탐색은 다른것과 유사하게 큐에서 뽑고, 종료조건인지 확인한 후 탐색을 하면서 조건에 맞는것만 큐에 넣는 방식으로 진행된다. 이 때, 먼저 만들어둔 에라토스테네스의 체를 사용해 각 숫자가 소수인지 확인할 수 있다. visit[] 배열도 똑같이 그 공간만큼 만들고, 탐색을 진행하면서 표시하게 된다.

int S, E;
std::cin >> S >> E;
std::queue<number> Q;
bool visit[10001];
bool found = false;
memset(visit, 0, sizeof(visit));
Q.push(number(S, 0));
while (!Q.empty())
{
    number cur = Q.front();
    Q.pop();

    if (cur.getNumber() == E){
        std::cout << cur.count << '\n'; 
        found = true;
        break;
    }
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            number next(cur.getNumber(), cur.count + 1);
            next[i] = j;
            if (next.getNumber() > 999 && next.getNumber() < 10000 && filter[next.getNumber()] && !visit[next.getNumber()])
            {
                Q.push(next);
                visit[next.getNumber()] = 1;
            }
        }
    }
}
if (!found)
    std::cout << "Impossible" << '\n';

 

탐색은 2D 맵과 거의 똑같다. 2차원으로 진행되는 탐색이 그냥 1차원으로 바뀌기만 한 것 같다.

---

전체 코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <string.h>
// PASS
int filter[10001];
struct number{
    int num[4];
    int count;
    int getNumber(){
        return this->num[0] * 1000 + this->num[1] * 100 + this->num[2] * 10 + this->num[3];
    }
    int& operator[](int idx){
        return num[idx];
    }
    number(int input, int count){
        this->num[3] = input % 10; input /= 10;
        this->num[2] = input % 10; input /= 10;
        this->num[1] = input % 10; input /= 10;
        this->num[0] = input % 10; input /= 10;
        this->count = count;
    }
    number() {}
};

int main()
{
    memset(filter, 1, sizeof(filter));

    filter[0] = 0;
    filter[1] = 0;
    for (int i = 2; i < 10000; i++)
    {
        if (filter[i])
        {
            for (int j = 2*i; j < 10000; j+=i)
                filter[j] = 0;
        }
    }

    // for (int i = 0; i < 10000; i++)
    //     if(filter[i])
    //         std::cout << i << " ";

    int T;
    std::cin >> T;
    for (int run = 0; run < T; run++)
    {
        int S, E;
        std::cin >> S >> E;
        std::queue<number> Q;
        bool visit[10001];
        bool found = false;
        memset(visit, 0, sizeof(visit));
        Q.push(number(S, 0));
        while (!Q.empty())
        {
            number cur = Q.front();
            Q.pop();

            if (cur.getNumber() == E){
                std::cout << cur.count << '\n'; 
                found = true;
                break;
            }
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    number next(cur.getNumber(), cur.count + 1);
                    next[i] = j;
                    if (next.getNumber() > 999 && next.getNumber() < 10000 && filter[next.getNumber()] && !visit[next.getNumber()])
                    {
                        Q.push(next);
                        visit[next.getNumber()] = 1;
                    }
                }
            }
        }
        if (!found)
            std::cout << "Impossible" << '\n';
    }

}

 

BFS, DFS는 계속 꾸준히 봐야겠다. 이게 어느정도 꼬는게 LCA같은 경우 원래 로직 틀에서 많이 바뀌지는 않았는데, BFS DFS의 경우 특이하게 꼬는 문제나 Cost계산, Visit처리의 다양성을 보면 진짜 엄청나게 많은 유형으로 만들 수 있는 것 같다.

 

오늘도 평온한 하루가 되길. 슨민.