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

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

1963번: 소수 경로

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, a, b;
int arr[10000], visited[10000];

void setting()
{
    memset(arr, 1, sizeof(arr));
    memset(visited, 0, sizeof(visited));
    arr[1]=0; //1은 소수

    for(int i=2; i<=9999; i++)
    {
        for(int j=i*2; j<=9999; j+=i)
        {
            arr[j] = 0; //소수 아닌 것들 (각 i의 배수들)
        }
    }
}

void bfs()
{
    queue<pii>q;
    q.push({a, 0});
    visited[a]=1;

    while(!q.empty())
    {
        auto[cur, cnt] = q.front(); q.pop();   

        if(cur == b) 
        {
            cout << cnt << "\n";
            return;
        }

        for(int i=0; i<4; i++) //4자리
        {
            for(int j=0; j<10; j++) //0~9
            {
                string s = to_string(cur); //변환을 위해 문자열로
                s[i] = j + '0'; //숫자 1개씩 바꿈
                int next = stoi(s); //다시 숫자로

                if(next < 1000 || next >= 10000) continue; //범위조건 (4자릿수 유지)
                if(!arr[next] || visited[next]) continue; //소수 or 방문체크
                
                visited[next]=1;
                q.push({next, cnt+1});
            }
        }
    }

    cout << "Impossible" << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> T;

    while(T--)
    {
        cin >> a >> b;
        setting();
        bfs();
    }


    return 0;
}

 

주어진 수의 범위만큼 미리 소수 판별을 해두고  bfs 탐색을 시작한다.

테스트케이스가 여러가지이므로 따로 소수 판별을 위한 함수를 만들어두고 매 테스트케이스마다 해당 함수를 실행시켜준다.

그리고 이때 방문체크용 배열도 같이 초기화하도록 하였다.

 

큐에 현재 숫자인 a와 현재 카운팅인 0을 넣고 bfs 탐색을 시작한다.

숫자가 4자리이므로 첫번째 반복문은 0~4까지 반복하게 된다.

이후 바로 또 반복문이 오는데 이는 현재 자릿수에 대해 0~9까지 선택하면서 체크하기 위함이다.

 

숫자의 특정 자릿수 원할하게 교체하기 위해 현재 수인 cur을 문자열로 바꿔준다.

이후 현재 자릿수인 i를 현재 선택된 수인 j로 바꿔주게된다.

바꿔줬으면 다시 숫자로 변환해준다.

 

해당 숫자는 4자릿수를 유지해야 하므로 1000보다 낮거나 9999보다 크면 안된다 이에 대한 범위조건을 체크해준다.

그리고 해당 숫자가 소수인지, 이미 방문했던 숫자인지도 체크해주고 모두 이상없다면 방문체크와 함께 큐에 현재 숫자와 카운팅을 1 더하여 넘겨준다.

 

이를 반복하여 목표 숫자인 b와 같아지면 여태 카운팅한 숫자를 출력해주면 된다.