[C++] 백준 - 1963 : 소수 경로

문제 링크

1963번: 소수 경로

 

 

풀이 )

  현재 입력받은 수에 대해서 한 자리씩 숫자를 하나씩 바꿔가면서 BFS를 한다.

  같은 수를 다시 Queue에 넣는 것을 방지하기 위해 visited 배열을 사용하여 방문 여부를 확인하여 방문한 경우 Queue에 넣지 않는다.

 

  한 자리씩 바꾸는 경우 현재 수 num, 자릿수 digit, 바꾸자하는 수 i를 매개변수로 받아 결과값을 반환하는 make( )를 만들었다. (제곱을 구하는 pow( )에서는 밑을 10으로 고정하여 지수만 입력받아 반환하도록 했다.)

  ex ) 1234에서 10^2의 자리수 2를 7로 바꾼다하면 make(1234, 2, 7)을 호출한다.

         1734바꾸면 되므로

• 10^2보다 큰 자리에 대해선 그대로 두기 위해 num/pow(digit+1)*pow(digit+1)
• 10^2자리에서는 pow(digit)*i
• 10^2이하 자리에서는 num%pow(digit);

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

bool prime[10000];

int pow(int num){
    if(!num)
        return 1;
    return 10*pow(num-1);
}

int make(int num, int digit, int i){
    return (num/pow(digit+1)*10+i)*pow(digit)+num%pow(digit);
}

int main(void){

    for(int i = 1000; i < 10000; ++i){
        prime[i] = true;
        for(int j = 2; j < 100; ++j){
            if(i%j==0){
                prime[i] = false;
                break;
            }
        }
    }

    int t;
    cin >> t;
    int a, b;
    while(t--){
        cin >> a >> b;

        queue<pair<int, int> > q;   // 숫자, 단계
        bool visited[10000] = {false, };
        q.push({a, 0});
        visited[a] = true;
        while(1){
            int tmp = q.front().first;
            int cnt = q.front().second;
            if(tmp == b){
                cout << cnt << '\n';
                break;
            }
            visited[tmp] = true;
            q.pop();

            for(int digit = 0; digit < 4; ++digit){
                for(int i = 0; i < 10; ++i){
                    if(digit == 3 && i == 0)
                        continue;
                    a = make(tmp, digit, i);
                    if(visited[a] || !prime[a])
                        continue;
                    q.push({a, cnt+1});
                }
            }
        }
    }
}