[C++] 백준 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을 출력한다.

 

 

---

 

 

문제 해결

DP(Dynamic Programming) 방법으로 풀릴까 싶어 30분이 넘도록 고민하다가 도저히 갈피를 잡을 수 없다고 판단해서 문제 태그를 살펴봤다.

 

소수, 정수론, 에라토스테네스의 체, 등등은 당연하지만.. 그 중에 눈에 띄는 태그가 있었는데 바로 "너비 우선 탐색"이다.

바로 코드 작성해서 맞추긴 했지만, BFS로 해결해야 함을 알아채는 것이 관건이었다.

 

 

알고리즘은 다음과 같다.

네 자리 중 한 자리씩 0부터 9까지 바꿔가는 문제로, 구현은 대략 5분 쯤 걸린 것 같다..

네 자리 중 한 자리를 바꿨을 때 수를 k라고 한다면 k가

(1) 1000 이상

(2) 소수

(3) 아직 큐에 추가되지(방문하지) 않은 수

위의 세 조건을 모두 만족하면 큐에 추가한다.

 

구현 과정에서 약간의 실수가 있었는데,

수를 0에서 9까지 바꿔서 판별한 후 다음 자릿수로 넘어가기 전에 바뀐 수를 다시 원래대로 복구해둬야 한다.

그렇지 않으면 한 턴에 한 자리가 아니라 여러 자리가 바뀌어 버리므로 원하는 결과를 얻을 수 없다.

 

 

 

코드

#include <iostream>
#include <queue>
using namespace std;

int t, a, b, tmp[4];
bool prime[10001] = { 1,1 };    // 소수면 0, 소수가 아니면 1

int toInt(int* ary) {
    int res = 0;

    for (int i = 0, m = 1000; i < 4; i++, m /= 10) {
        res += ary[i] * m;
    }
    return res;
}

int bfs() {
    bool visit[10000] = {};

    queue<pair<int, int>> q;

    visit[a] = 1;
    q.push({ a,0 });

    while (!q.empty()) {
        int p = q.front().first, cnt = q.front().second;
        q.pop();

        if (p == b) return cnt;

        for (int i = 0, m = 1000; i < 4; i++, m /= 10) {
            tmp[i] = p / m;
            p %= m;
        }

        for (int i = 0; i < 4; i++) {
            int origin = tmp[i];		// 원래 값 기억

            for (int j = 0; j < 10; j++) {
                tmp[i] = j;
                int k = toInt(tmp);

                if (k >= 1000 && !prime[k] && !visit[k]) {
                    q.push({ k, cnt + 1 });
                    visit[k] = 1;
                }
            }

            tmp[i] = origin;	// 해당 자릿수 반복 끝나면 원상태로 복구
        }
    }

    return -1;
}

int main() {

    for (int i = 2; i * i < 10000; i++)
        for (int j = 2 * i; j <= 10000; j += i) {
            if (prime[i]) break;
            prime[j] = 1;
        }
    
    cin >> t;
    
    while (t--) {
        cin >> a >> b;

        int ans = bfs();

        if (ans < 0) cout << "Impossible" << '\n';
        else cout << ans << '\n';

    }  
}