[1963] 소수 경로

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

1963 - 소수 경로

본문

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데… 다음 소수를 무엇으로 할지 고민중이야”
• “그럼 8179로 해”
• “흠… 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데… 예를 들면… 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠…역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 $A$에서 $B$로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 $T$가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

---

풀이

사용할 비밀번호들은 모두 소수이므로, 소수들을 먼저 찾아놓도록 하자. 4자리 수만을 비밀번호로 사용할 수 있으므로, 1000 ~ 9999까지의 소수만 찾아놓으면 된다. 수의 범위가 작으므로 모든 소수를 찾을 수 있는 에라토스테네스의 체를 활용하여 소수를 찾아놓도록 한다.

이후 시작 번호로부터 도착 번호로 갈 수 있는지 탐색해야한다. 탐색 횟수도 같이 구하면서 최단경로를 찾아야하므로 BFS 탐색을 통해 문제를 해결할 수 있다. 문제에서 탐색에 필요한 그래프가 주어지지는 않는데, 각 수들은 ‘본인의 수에서 1개의 숫자만 달라지는 경우’에 대해 모두 변할 수 있으므로 한 자릿수만 다른 수들에는 가중치가 1인 경로가 존재한다고 이해할 수 있다. 이에 대해 BFS 탐색을 돌리고, 최단경로를 찾으면 해결되는 문제.

• 참고 알고리즘 : 소수 판별법 - 에라토스테네스의 체, BFS 탐색

코드

사용 언어 : C

최종 수정일 : 2024 / 4 / 11

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

const int INF = 987654321;
#define MAX_IDX 10000

bool isNotPrime[MAX_IDX] = {true, true};

void prime_init() {
    for (int i = 2; i < MAX_IDX; ++i) {
        if (isNotPrime[i] == false) {
            for (int j = i * 2; j < MAX_IDX; j += i) {
                isNotPrime[j] = true;
            }
        }
    }
    return;
}

typedef struct QueueNode {
    int num;
    int cnt;
} QN;

int t;
int a, b;
QN q[MAX_IDX + 1];
bool visit[MAX_IDX + 1];
int front, rear;
int retval;

int main() {
    prime_init();
    scanf("%d", &t);

    while (t--) {
        scanf("%d %d", &a, &b);

        for (int i = 0; i < MAX_IDX; ++i) {
            visit[i] = false;
        }
        retval = INF;
        front = rear = 0;
        visit[a] = true;
        q[rear++] = (QN){a, 0};

        while (front < rear) {
            QN node = q[front++];
            if (node.num == b) {
                retval = node.cnt;
                break;
            }

            for (int digit = 1; digit < MAX_IDX; digit *= 10) {
                int std = node.num - (((node.num % (digit * 10)) / digit) * digit);

                for (int j = 0; j < 10; ++j) {
                    int temp = std + (j * digit);

                    if (temp < 1000) {
                        continue;
                    } else if (isNotPrime[temp] == false && visit[temp] == false) {
                        visit[temp] = true;
                        q[rear++] = (QN){temp, node.cnt + 1};
                    }
                }
            }
        }

        if (retval < INF) {
            printf("%d\n", retval);
        } else {
            printf("Impossible\n");
        }
    }
    return 0;
}