[백준1963] 소수 경로

정답률이 높았지만, 다른 정답률이 높은 문제들에 비해서 긴 소스코드를 작성해야 하는 문제였습니다.

BFS와 에라토스테네스의 체의 개념을 확실하게 알고 있어야 풀 수 있는 문제입니다.

( BFS로 푸는 이유 => 모든 간선의 비용이 1이다 )

저 같은 경우는, 하나의 큐와 1부터 10000까지 배열을 2개 만들어

queue q는 BFS 접근을 하기 위하여 사용하였고

int visit [10000] 배열은 방문 여부를 확인하는 배열이며, 값은 소수 변환에 필요한 횟수를 가지게 구현하고

bool c [10000] 배열은 소수인지 아닌지 확인하는 배열을 구현하였습니다.



추가적으로는 배열이 아닌 struct { int a, bool b} 혹은  vector<pair<int,bool>> c 컨테이너를 사용하여

충분히 풀 수 있는 문제입니다.

출처 : 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을 출력한다.

예제 입력 1

3
1033 8179
1373 8017
1033 1033

예제 출력 1

6
7
0

소스코드

#include<iostream>
#include<queue>
#include<cstring>
 
using namespace std;
 
// 1000부터 9999까지 배열만 사용한다. 
// bool c => 소수이면 false, 소수가 아니면 true이다.
// int visit => 방문했으면 > 0, 방문하지 않았으면 0 이다. 
bool c[10000];
int visit[10000];
queue<int> q;
 
// swap을 사용한 큐 비우기 
void clearQueue(queue<int> &Queue)
{
    queue<int> empty;
    swap(Queue, empty);
}
 
// 소수인지 아닌지 확인하는 메소드 
bool isPrime(int num) {
    if (c[num] == false)
        return true;
    else
        return false;
}
 
// 소수를 저장하기 위해서 사용하는 함수 
void eratos(int begin, int end) {
    // 1은 소수이다. 
    c[1] = true;
    for (int i = 2; i*i <= end; i++) {
        if (c[i] == false) {
            for (int j = i * i; j <= end; j += i) {
                c[j] = true;
            }
        }
    }
}
 
// 숫자 n의 what자리를 to로 바꾼다.
// change_numb(1234,1,3) -> 3234 
int change_numb(int n, int what, int to) {
    int k = n;
    if (what == 1) {
        k -= (n / 1000) * 1000;
        k += to * 1000;
    }
    else if (what == 2) {
        k -= ((n / 100) % 10) * 100;
        k += to * 100;
    }
    else if (what == 3) {
        k -= ((n % 100) / 10) * 10;
        k += to * 10;
    }
    else if (what == 4) {
        k -= n % 10;
        k += to;
    }
    return k;
}
 
// bfs 탐색
void bfs(int from, int to) {
    q.push(from);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        // 첫번째자리 부터 네번째자리 까지 
        for (int i = 1; i <= 4; i++) { 
            // 해당자리 숫자를 0부터 9까지 바꾸어본다. 
            for (int j = 0; j <= 9; j++) {
                int next = change_numb(now, i, j);
                // next가 소수 && 방문하지 않았고 && 4자리일때 
                if (isPrime(next) && visit[next] == 0 && next >= 1000) {
                    visit[next] = visit[now] + 1;
                    q.push(next);
                    if (next == to) {
                        cout << visit[next]-1 << '\n';        // 시작 위치가 1이기 때문에 -1 연산을 시켜준다. 
                        return;
                    }
                }
            }
        }
    }
    cout << "Impossible" << '\n'; 
}
 
int main() {
    int t;
    cin >> t;
 
    eratos(1, 10000);                        // 편의상 1부터 10000까지 소수를 구한다.
    
    while (t--) {
        int from, to;
        cin >> from >> to;
        if(from == to)                        // 두 소수가 같은 경우 
            cout << '0' << '\n';
        else{                                // 두 소수가 달라서 연산이 필요한 경우 
            visit[from] = 1;                // 시작 위치 비용 1로 계산 (true) 
            bfs(from, to);
            memset(visit,0,sizeof(visit));    // 방문한 기록 초기화 
            clearQueue(q);                    // 큐 초기화 
        }
    }
    return 0;
}
 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.