[백준 1963] 소수 경로 [C]

백준 - 1963

---

풀이

네 자리 수를 하나씩 바꾼 수가 소수이면서, 중복을 피하기 위해 기존에 확인한 수가 아닌 경우에만, Queue에 담아주고, 

자리수를 바꾸기 전의 수의 변환 횟수에 1을 더한 값을 자리수를 바꾼 후 숫자의 변환 횟수에 입력해주었다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <memory.h>
#include <math.h>
#define MAX 10000
bool cNum[MAX];
int cnt[MAX], queue[MAX];

void bfs(int old, int pw){
    int front = -1, rear = -1, n;
    cnt[queue[++rear] = old] = 0;
    while (front < rear){
        if ((n = queue[++front]) == pw) return;
		
        for (int i = 0; i < 4; i++){
            int digit[4] = {n/1000, (n/100)%10, (n/10)%10, n%10};
			
            for (int j = (i ? 0: 1); j < 10; j++)
                if (digit[i] != j){
                    digit[i] = j;
                    int temp = digit[0]*1000 + digit[1]*100 + digit[2]*10 + digit[3];
                    if (!cNum[temp] && cnt[temp] == -1)
                        cnt[queue[++rear] = temp] = cnt[n] + 1;
                }	
        }	
    }
}
int main(){
    int sq = sqrt(MAX);
    for (int i = 2; i <= sq; i++)
        if (!cNum[i])
            for (int j = 2*i; j < MAX; j += i)
                cNum[j] = true;
	
    int T;
    scanf("%d", &T);
    while (T--){
        memset(cnt, -1, sizeof(cnt));
        int old, pw;
        scanf("%d %d", &old, &pw);
        bfs(old, pw);
        if (cnt[pw] == -1) puts("Impossible");
        else printf("%d\n", cnt[pw]);
    }	
}

---

출처

1963번: 소수 경로