[ 백준 1963 ] 소수경로 (C++)

백준의 소수경로(1963) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 자릿수가 4인 정수가 주어진다. 이 숫자를 자릿수의 있는 각각의 숫자들은 하나씩 바꿔가면서 원하는 숫자가 될 때 까지

  몇번 바꿔야 하는지 최소 횟수를 출력하는 문제인데, 숫자들을 바꿀 때 그 숫자들은 소수 여야 한다.

2. 이 문제에서 가장 중요한 부분은 소수인지 체크하는 방법이라고 생각한다. 이 부분은 에라토스테네스의 체 라는 방식으로

   배열을 하나 만들어서 소수인 놈들에게만 True로 설정해주고, 소수가 아닌 놈들에게는 false를 설정해주고 이 배열을 통해서

   확인하는 방식이다.

   그렇다면 소수인 놈들을 어떻게 True라는 값으로 바꿔줄까?

    memset(EraTos, true, sizeof(EraTos));
    for (int i = 2; i < MAX; i++)
    {
        for (int j = 2; i*j < MAX; j++)
        {
            EraTos[i*j] = false;
        }
    }

    위의 코드를 한번 봐보자. 소수라는 것은 나눌 수 있는 수가 1과 자기자신 2개 뿐인 숫자이다. 즉, 어떤 수의 배수라면 그 수

    는 소수가 아닐 것이다.

    위의 코드는 어렵지 않은 코드이다. 코드를 간략하게 설명해보자면, 2부터 최댓값 까지 계속 반복하면서

    이 숫자들의 배수들은 모두 false로 체크해주는 코드이다. 그렇다면 저렇게 false로 체크된 값이 아닌 true인 값들은

    소수일 것이다.

3. 본격적인 문제이다. 기본적인 BFS()만 할 줄 안다면 어렵지 않을 것이다. Queue에 처음 시작 숫자를 push해주고

   그 숫자를 문자열 처리를 하여, 자릿수마다 바꿀 수 있는 모든 숫자들을 바꿔주고, 소수이면서 탐색하지 않은 숫자들에

   대해서만 계속해서 push를 해주고 탐색을 반복한다면 쉽게 구할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
#include<string>
 
#define endl "\n"
#define MAX 10000
using namespace std;
 
bool EraTos[MAX];
bool Visit[MAX];
 
int Start, End;
 
void Initialize()
{
    memset(EraTos, true, sizeof(EraTos));
    for (int i = 2; i < MAX; i++)
    {
        for (int j = 2; i*j < MAX; j++)
        {
            EraTos[i*j] = false;
        }
    }
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> Start >> End;
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(Start, 0));
    Visit[Start] = true;
 
    while (Q.empty() == 0)
    {
        int Cur_Num = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur_Num == End)
        {
            cout << Cnt << endl;
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int Next_Num;
            for (int j = 0; j < 10; j++)
            {
                string s = to_string(Cur_Num);
                s[i] = j + '0';
                Next_Num = stoi(s);
 
                if (EraTos[Next_Num] == false) continue;
                if (Visit[Next_Num] == true) continue;
                if (Next_Num >= 10000 || Next_Num < 1000) continue;
 
                Visit[Next_Num] = true;
                Q.push(make_pair(Next_Num, Cnt + 1));                
            }
        }
    }
    cout << "Impossible" << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}