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

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

1963번: 소수 경로

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 선언하고 에라토스테네스의 채로 소수를 구분한다.

    cin >> n;
    separate_prime(); // 에라토스테네스의 체
    while(n--){
        int from,to,ans;
        cin >> from >> to;
        ans = bfs(from,to);
        if(ans==-1) cout << "Impossible" << "\n";
        else cout << ans << "\n";
        memset(visited, false, sizeof(visited));
    }

void separate_prime(){
    prime[2] = false, prime[3] = false, prime[5] = false, prime[7] = false;
    for(int i=2; i<MAX; i++){
        if(!prime[i]){
            for(int j=i+i; j<MAX; j+=i){
                prime[j] = true; // 결국 false인 경우만 소수
            }
        }
    }
}

그런 다음 시작값과 목표값을 매개변수로 넣어 BFS를 진행한다.

 

2. 아래는 BFS의 코드이다.

struct tc{
    int a,b;
};
int bfs(int from, int to){
    queue<tc> q;
    q.push({0,from}); (1) 
    while(!q.empty()){ // prime이 false여야 소수
        int cnt = q.front().a;
        int now = q.front().b;
        if(now==to) return cnt;
        q.pop();
        if(now%10!=to%10&&now/10==to/10) return cnt+1; // (2)
        else if((now/10)%10!=(to/10)%10&&now%10==to%10&&now/100==to/100) return cnt+1; 
        else if((now/100)%10!=(to/100)%10&&now/1000==to/1000&&now%100==to%100) return cnt+1; 
        else if(now/1000!=to/1000&&now%1000==to%1000) return cnt+1;
        for(int i=1001; i<MAX; i++){ // (3)
            if(!prime[i]&&!visited[i]&&now%10!=i%10&&now/10==i/10){ // (4)
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/10)%10!=(i/10)%10&&now%10==i%10&&now/100==i/100){
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/100)%10!=(i/100)%10&&now%100==i%100&&now/1000==i/1000){
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/1000)!=(i/1000)&&now%1000==i%1000){
                visited[i] = true;
                q.push({cnt+1,i});
            }
        }
    }
    return -1; // (5)
}

(1) 큐에 최초의 숫자 변화 횟수 0과 현재 숫자 from을 넣어준다.

(2) 2번 코드의 경우, 각각 1의자리에서 1000의 자리까지 단 하나의 자리만 정답값과 다른 경우, 현재 숫자 변화 횟수에서 +1을 반환하는 코드이다.

+ 참고로 (2)번 문단의 코드를 적지 않아도 정답을 구할 수 있으나, 이 코드를 적어주면 시간이 약 12ms 빠른 답을 출력할 수 있다.

(3) for문의 조건을 보면 i=1001; i<MAX(=10000)이다. 1001부터 시작하는 이유는 4자리 숫자중 최초의 소수는 1001이기 때문이다. 또한 문제를 잘 읽어보면 필요시 현재 숫자보다 작은 소수로 최단거리가 인정될 수 있다.

(4) 4번 코드의 경우, 1001부터 최대값까지 해당 숫자가 소수에 해당되며, 아직 방문하지 않은 숫자이며, 동시에 현재 q.front()에 저장되었던 숫자와 비교했을때 1에서 1000의 자리 중 단 한 자리만 다른 경우에 한해서 방문표시를 하고 큐에 삽입하는 코드이다. 

(5) 만약 큐가 비었을 경우 정답을 찾지 못했다는 뜻이므로 -1을 반환한다.

 

3. BFS를 종료하고 main함수로 복귀했을때, 정답을 출력하고 visited 배열은 false로 초기화해준다.

    while(n--){
        int from,to,ans;
        cin >> from >> to;
        ans = bfs(from,to);
        if(ans==-1) cout << "Impossible" << "\n";
        else cout << ans << "\n";
        memset(visited, false, sizeof(visited));
    }

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define MAX 10000
using namespace std;

int n;
bool prime[MAX], visited[MAX];
struct tc{
    int a,b;
};
void separate_prime(){
    prime[2] = false, prime[3] = false, prime[5] = false, prime[7] = false;
    for(int i=2; i<MAX; i++){
        if(!prime[i]){
            for(int j=i+i; j<MAX; j+=i){
                prime[j] = true; 
            }
        }
    }
}

int bfs(int from, int to){
    queue<tc> q;
    q.push({0,from});
    while(!q.empty()){ // prime이 false여야 소수
        int cnt = q.front().a;
        int now = q.front().b;
        if(now==to) return cnt;
        q.pop();
        if(now%10!=to%10&&now/10==to/10) return cnt+1; // 정답에서 첫 번째 자리만 다름
        else if((now/10)%10!=(to/10)%10&&now%10==to%10&&now/100==to/100) return cnt+1; // 두 번째 자리
        else if((now/100)%10!=(to/100)%10&&now/1000==to/1000&&now%100==to%100) return cnt+1; // 세 번째 자리
        else if(now/1000!=to/1000&&now%1000==to%1000) return cnt+1; // 네 번째
        for(int i=1001; i<MAX; i++){
            if(!prime[i]&&!visited[i]&&now%10!=i%10&&now/10==i/10){ // 해당 소수와 첫 번째 자리만 다름
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/10)%10!=(i/10)%10&&now%10==i%10&&now/100==i/100){ // 두 번째 자리
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/100)%10!=(i/100)%10&&now%100==i%100&&now/1000==i/1000){ // 세 번째 자리
                visited[i] = true;
                q.push({cnt+1,i});
            }
            else if(!prime[i]&&!visited[i]&&(now/1000)!=(i/1000)&&now%1000==i%1000){ // 네 번째 자리
                visited[i] = true;
                q.push({cnt+1,i});
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    separate_prime();
    while(n--){
        int from,to,ans;
        cin >> from >> to;
        ans = bfs(from,to);
        if(ans==-1) cout << "Impossible" << "\n";
        else cout << ans << "\n";
        memset(visited, false, sizeof(visited));
    }
    return 0;
}

이 코드는 48ms가 소비되었다.