[Jungol] 정올 1336 소수와 함께 하는 여행

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=30

 Input 
1033 8179

 Output 

6

 

출발점으로 부터 숫자 자릿수 차이가 한 개가 발생하는 숫자들을 탐색해 갑니다.

이때, 자릿수 차이와 함께 소수여야 하므로 1000 ~ 9999까지의 수 중

에라토스테네스의 체를 이용해서 미리 소수를 구합니다.

※ 코드에서는 prime[i] = 1인 경우, 숫자 i는 소수가 아닙니다.

 

두 수의 자릿수 일치 정도 확인

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 10000;
struct Bus {
    int num, time;
} que[LM];
int start, end;
int visited[LM], prime[LM]; // 0 ~ 9999
int fr, re;
 
void make_prime() {
    int i, j;
    prime[0] = prime[1] = 1;
    for (i = 2; i < LM; i++) {
        if (prime[i] == 1) continue;
        for (j = i + i; j < LM; j += i) {
            // 소수가 아닌 경우 = 1
            prime[j] = 1; 
        }
    }
}
 
// 두 수의 자릿수 중 일치하지 않는 숫자의 개수
int check(int A, int B) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        if (A % 10 != B % 10) cnt++;
        A /= 10; B /= 10;
    }
    return cnt != 1;
}
 
int BFS() {
    Bus cur;
    que[re++] = { start, 0 };
    visited[start] = 1;
 
    while (fr < re) {
        cur = que[fr++];
 
        if (cur.num == end) {
            return cur.time;
        }
 
        for (int next = 1000; next < LM; ++next) {
            // 이미 방문하였거나 소수가 아닌 경우
            if (visited[next] || prime[next]) continue;
 
            // 두 수의 자릿수 차이가 1인 아닌 경우
            if (check(cur.num, next)) continue;
 
            // 방문 표시
            visited[next] = 1;
            que[re++] = { next, cur.time + 1 };
        }
    }
    return -1;
}
 
int main() {
    make_prime();
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &start, &end);
    printf("%d\n", BFS());
}