[BFS] 1963번 소수 경로

1963번 소수경로

 

https://www.acmicpc.net/problem/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을 출력한다.

 

예제 입력

3
1033 8179
1373 8017
1033 1033

 

예제 출력

6
7
0

 

해결방법

• 두 네자리 소수 N과 M이 주어졌을 때
• N을 M으로 바꾸는 최소 변환 횟수를 구하는 문제
• 한 번에 N에서 한 자리만 바꿀 수 있고
• 바꾼 숫자도 소수여야 한다

미리 모든 소수를 구해놓는다! 어짜피 네자리 수이기 때문에 10,000 이하가 된다.

 

네 자리 소수 num을 i번째 인덱스를 c로 바꾸는 함수를 구현하는게 핵심이다

int change(int num, int i, int c){
    // 첫 번째 자리를 0으로 바꾸는 경우는 -1을 리턴함
    if(i==0 && c==0) return -1;
    
    string tmp = to_string(num);
    tmp[i] = c + '0';
    return stoi(tmp); 
}

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10000
#define INF 987654321
using namespace std;

int t;
int n,m;
int ans;

bool visit[MAX];
int dist[MAX];

// 소수인지 판별하는 함수
bool is_prime(int n){
    for(int i=2; i<n; i++){
        if(n%i == 0) return false;
    }
    return true;
}

// 네 자리 소수 num의 i번째 수를 c로 변환시키는 함수
int change(int num,int i, int c){
    if(i == 0 && c ==0) return -1;
    
    string tmp = to_string(num);
    tmp[i] = c + '0';
    return stoi(tmp);
}

void bfs(int nn,int mm){
    queue<int> q;
    q.push(nn);
    visit[nn] = true;
    dist[nn] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        if(now == mm){
            break;
        }
        
        for(int i=0; i<4; i++){
            for(int j=0; j<=9; j++){
                int next = change(now, i, j);
                if(next!=-1){
                    if(!visit[next] && is_prime(next)){
                        visit[next] = true;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }
                }
            }
        }
    }
    printf("%d\n",dist[mm]);
}

int main(int argc, const char * argv[]) {
    scanf("%d",&t);
    for(int i=0; i<t; i++){
        memset(visit,false,sizeof(visit));
        memset(dist,-1,sizeof(dist));
        scanf("%d %d",&n,&m);
        ans = INF;
        bfs(n,m);
    }
}