백준 1963 - 소수 경로(C++)

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

1963번: 소수 경로

에라토스테네스의 체 + BFS를 이용하는 문제였습니다!

문제 조건

출력 예시

 

문제 접근 방법

1. 에라토스테네스의 체를 이용해 1000~9999까지의 소수를 구한다

2. 소수 한 쌍을 입력받은 뒤, 소수 경로를 구하는 BFS에 저장한다.

3. answer의 값에 따라 출력한다.

 

 

문제 접근 방법 - 1번

void find_prime_number() {
    for (int i = 2; i <= 9999; i++) {
        prime_number[i] = 1;
    }
    for (int i = 2; i <= sqrt(9999); i++) {
        if (prime_number[i] == 0) continue;
        for (int j = i * i; j <= 9999; j += i) {
            prime_number[j] = 0;
        }
    }
}

해당 코드는 에라토스테네스의 체 코드입니다.

해당 함수를 통해서 1000~9999까지의 소수를 찾았습니다.

 

문제 접근 방법 - 2번+3번

void bfs(int start, int finish) {
    int answer = -1;
    check[start] = 1;
    queue<qu> q;
    q.push({ start, 0 });
    while (!q.empty()) {
        int num = q.front().num;
        int cnt = q.front().cnt;
        if (num == finish) {
            answer = cnt;
            break;
        }
        q.pop();
        int num1 = num - num % 10;
        int num2 = num - num % 100 + num % 10;
        int num3 = num - num % 1000 + num % 100;
        int num4 = num % 1000;
        for (int i = 0; i <= 9; i++) {
            int num_1 = num1 + 1 * i;
            int num_2 = num2 + 10 * i;
            int num_3 = num3 + 100 * i;
            int num_4 = num4 + 1000 * i;
            if (num_1 >= 1000 && check[num_1] == 0 && prime_number[num_1] == 1) {
                check[num_1] = 1;
                q.push({ num_1, cnt + 1 });
            }
            if (num_2 >= 1000 && check[num_2] == 0 && prime_number[num_2] == 1) {
                check[num_2] = 1;
                q.push({ num_2, cnt + 1 });
            }
            if (num_3 >= 1000 && check[num_3] == 0 && prime_number[num_3] == 1) {
                check[num_3] = 1;
                q.push({ num_3, cnt + 1 });
            }
            if (num_4 >= 1000 && check[num_4] == 0 && prime_number[num_4] == 1) {
                check[num_4] = 1;
                q.push({ num_4, cnt + 1 });
            }
        }
    }
    if (answer == -1) cout << "Impossible" << "\n";
    else cout << answer << "\n";
}

소수 경로를 구하는 BFS코드입니다.

구조체 큐를 이용해, 현재 소수와 몇번 이동했는지를 저장했습니다.

소수를 변경하는 방법은 4가지입니다.

1. 1의 자리를 변경

2. 10의 자리를 변경

3. 100의 자리를 변경

4. 1000의 자리를 변경

4가지 모두를 동시에 해주기 위해서 각각 변수들을 선언한 뒤, 해당 자릿수를 0으로 만들었습니다 -> 예를 들어 1033일 경우,  1030으로 만든 뒤, 1030 ~ 1039까지 모두 살펴봤습니다. 이를 4경우 모두 했습니다. 

변경한 소수가 전에 방문하지 않았으며, 1000이상이고, 소수일 경우에만 큐에 다시 넣었습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int prime_number[10001];
int test_case;
int check[10001];
typedef struct qu {
    int num;
    int cnt;
}qu;

void find_prime_number() {
    for (int i = 2; i <= 9999; i++) {
        prime_number[i] = 1;
    }
    for (int i = 2; i <= sqrt(9999); i++) {
        if (prime_number[i] == 0) continue;
        for (int j = i * i; j <= 9999; j += i) {
            prime_number[j] = 0;
        }
    }
}

void bfs(int start, int finish) {
    int answer = -1;
    check[start] = 1;
    queue<qu> q;
    q.push({ start, 0 });
    while (!q.empty()) {
        int num = q.front().num;
        int cnt = q.front().cnt;
        if (num == finish) {
            answer = cnt;
            break;
        }
        q.pop();
        int num1 = num - num % 10;
        int num2 = num - num % 100 + num % 10;
        int num3 = num - num % 1000 + num % 100;
        int num4 = num % 1000;
        for (int i = 0; i <= 9; i++) {
            int num_1 = num1 + 1 * i;
            int num_2 = num2 + 10 * i;
            int num_3 = num3 + 100 * i;
            int num_4 = num4 + 1000 * i;
            if (num_1 >= 1000 && check[num_1] == 0 && prime_number[num_1] == 1) {
                check[num_1] = 1;
                q.push({ num_1, cnt + 1 });
            }
            if (num_2 >= 1000 && check[num_2] == 0 && prime_number[num_2] == 1) {
                check[num_2] = 1;
                q.push({ num_2, cnt + 1 });
            }
            if (num_3 >= 1000 && check[num_3] == 0 && prime_number[num_3] == 1) {
                check[num_3] = 1;
                q.push({ num_3, cnt + 1 });
            }
            if (num_4 >= 1000 && check[num_4] == 0 && prime_number[num_4] == 1) {
                check[num_4] = 1;
                q.push({ num_4, cnt + 1 });
            }
        }
    }
    if (answer == -1) cout << "Impossible" << "\n";
    else cout << answer << "\n";
}

void solve(int start, int finish) {
    memset(check, 0, sizeof(check));
    bfs(start, finish);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    find_prime_number();
    cin >> test_case;
    for (int k = 0; k < test_case; k++) {
        int N, M;
        cin >> N >> M;
        solve(N, M);
    }
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!