백준 1963 - 소수 경로

 

 

문제 설명

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

https://www.acmicpc.net/problem/1963

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 현재 비밀번호에서 목표한 비밀번호까지 소수로만 변경했을 때 최소 몇 단계의 변환이 필요한지 구해야 한다.

 

우선, 해당 문제는 크게 두 가지로 나눌 수 있다.

• 어떠한 수가 소수인지 판별
• 최소 단계로 변환

 

어떠한 수가 소수인지 판별하는 것은 간단하다.

a라는 수가 소수인지 판별하기 위해서는 1부터 $sqrt(a)$까지 반복하며 나누어 떨어지는지 확인하면 된다.

하지만, 이 문제에서는 T번의 testcase를 구해야 하며 9999까지의 수를 계속 판별한다면 시간초과가 발생할 것이다.

따라서, 1부터 9999까지의 수들이 소수인지 미리 판별하는 것이 좋다.

에라토스테네스의 체를 활용한다면 간단하게 구할 수 있다.

for (int i = 2; i * i < MAX; i++)
{
    if (isPrime[i]) 
    {
        for (int k = i * i; k < MAX; k += i) 
        {
            isPrime[k] = false;
        }
    }
}

 

이제, 현재 비밀번호로부터 목표 비밀번호까지 변환하는 작업만 수행하면 된다.

해당 작업은 bfs를 통해 해결할 수 있다.

총 4자리의 수를 0~9까지 변경해 보며 소수일 때만 큐에 넣어주면 된다.

단, 변경한 수가 1000 미만이라면 문제의 조건에 의해 제외해야 한다.

또한, 같은 수를 여러 번 판단할 필요는 없으니 중복체크를 해주는 것이 좋다.

queue<string> q;
q.push(currentPwd);

bool bFind = false;
set<string> visited;

int depth = 0;
while (!q.empty())
{
    int size = q.size();

    for (int k = 0; k < size; k++)
    {
        auto current = q.front();
        q.pop();

        if (visited.count(current)) continue;
        visited.insert(current);

        //i번째 자리를 j로 바꿈
        for (int i = 0; i < 4; i++)
        {
            if (bFind) break;
            for (int j = 0; j < 10; j++)
            {
                string next = current;
                next[i] = j + '0';

                if (next == nextPwd)
                {
                    bFind = true;
                    break;
                }

                if (CheckPrime(next) && visited.count(next) == 0)
                {
                    q.push(next);
                }
            }
        }
    }

    depth++;

    if (bFind)
    {
        cout << depth << "\n";
        break;
    }
}

if (!bFind) cout << "Impossible\n";

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T;
string currentPwd, nextPwd;
const int MAX = 10'000;
vector<bool> isPrime(MAX, true);

bool CheckPrime(string pwd)
{
    int num = 0;

    for (int i = 0; i < 4; i++)
    {
        num *= 10;
        num += pwd[i] - '0';
    }

    return isPrime[num] && 999 < num;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;

    cin >> T;

    for (int i = 2; i * i < MAX; i++)
    {
        if (isPrime[i]) 
        {
            for (int k = i * i; k < MAX; k += i) 
            {
                isPrime[k] = false;
            }
        }
    }

    while (T--)
    {
        cin >> currentPwd >> nextPwd;

        if (currentPwd == nextPwd)
        {
            cout << 0 << "\n";
            continue;
        }

        queue<string> q;
        q.push(currentPwd);

        bool bFind = false;
        set<string> visited;

        int depth = 0;
        while (!q.empty())
        {
            int size = q.size();

            for (int k = 0; k < size; k++)
            {
                auto current = q.front();
                q.pop();

                if (visited.count(current)) continue;
                visited.insert(current);

                //i번째 자리를 j로 바꿈
                for (int i = 0; i < 4; i++)
                {
                    if (bFind) break;
                    for (int j = 0; j < 10; j++)
                    {
                        string next = current;
                        next[i] = j + '0';

                        if (next == nextPwd)
                        {
                            bFind = true;
                            break;
                        }

                        if (CheckPrime(next) && visited.count(next) == 0)
                        {
                            q.push(next);
                        }
                    }
                }
            }

            depth++;

            if (bFind)
            {
                cout << depth << "\n";
                break;
            }
        }

        if (!bFind) cout << "Impossible\n";
    }

    return 0;
}

---