백준 1963번 소수 경로

문제 링크입니다: https://www.acmicpc.net/problem/1963

오랜만에 에라토스테네스의 체와 함께 BFS(Breadth First Search) 알고리즘을 사용하여 푸는 문제였습니다.

에라토스테네스의 체를 통해 우선 4자리 소수를 미리 구해놓은 뒤에 한자리씩 숫자를 바꿔가며 BFS를 적용하면 풀리는 문제였습니다.

주의할 점은, 4자리 소수이기 떄문에 천의 자리 수가 0이면 안됩니다!!

#include <iostream>

#include <queue>

#include <cmath>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000;

 

int start, destination;

int minFactor[MAX]; //minFactor[i] -> i의 가장 작은 소인수(i가 소수인 경우 자기 자신)

int cache[MAX];

 

//에라토스테네스의 체

void eratosthenes(void)

{

        //1은 항상 예외

        minFactor[0] = minFactor[1] = -1;

        //모든 숫자를 처음에는 소수로 표시

        for (int i = 2; i < MAX; i++)

                 minFactor[i] = i;

        //에라토스테네스의 체 수행

        for (int i = 2; i * i < MAX; i++) //sqrt(MAX)=100

                 if (minFactor[i] == i)

                         for (int j = i * i; j < MAX; j += i)

                                 //아직 약수를 본 적 없는 숫자인 경우 i를 써둔다

                                 if (minFactor[j] == j)

                                          minFactor[j] = i;

}

 

int BFS(void)

{

        memset(cache, 0, sizeof(cache));

 

        queue<int> q;

        q.push(start);

        cache[start] = 1;

 

        while (!q.empty())

        {

                 int curNum = q.front();

                 q.pop();

 

                 if (curNum == destination)

                         return cache[curNum] - 1;

 

                 //현재 숫자 천의 자리숫자부터

                 int digit[4] = { curNum / 1000, (curNum / 100) % 10, (curNum / 10) % 10, curNum % 10 };

 

                 for (int i = 0; i < 4; i++)

                 {

                         //천의 자리 수는 0이면 안된다

                         if (i == 0)

                         {

                                 for (int j = 1; j < 10; j++)

                                 {

                                          int changeNum=0;

                                          for (int k = 0; k < 4; k++)

                                                  if (i != k)

                                                          changeNum += digit[k] * pow(10, 3 - k);

                                                  else

                                                          changeNum += j * pow(10, 3 - k);

                                          //바뀐 숫자가 소수이고

                                          if (minFactor[changeNum] == changeNum && cache[changeNum] == 0)

                                          {

                                                  cache[changeNum] = cache[curNum] + 1;

                                                  q.push(changeNum);

                                          }

                                 }

                         }

                         else

                         {

                                 for (int j = 0; j < 10; j++)

                                 {

                                          int changeNum = 0;

                                          for (int k = 0; k < 4; k++)

                                                  if (i != k)

                                                          changeNum += digit[k] * pow(10, 3 - k);

                                                  else

                                                          changeNum += j * pow(10, 3 - k);

                                          //바뀐 숫자가 소수이고

                                          if (minFactor[changeNum] == changeNum && cache[changeNum] == 0)

                                          {

                                                  cache[changeNum] = cache[curNum] + 1;

                                                  q.push(changeNum);

                                          }

                                 }

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        eratosthenes();

 

        for (int i = 0; i < test_case; i++)

        {

                 cin >> start >> destination;

 

                 int result = BFS();

                 if (result == -1)

                         cout << "Impossible" << endl;

                 else

                         cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~