[1963번] 소수경로

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

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

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

[예제입력]

(첫 줄에 Test Case 수 T가 주어진다)

3

1033 8179

1373 8017

1033 1033

[예제출력]

(불가능할 경우 'Impossible'을 출력한다)

6

7

0

[풀이를 위한 개념]

http://twoearth.tistory.com/3?category=809135 (숨바꼭질) 문제에서 사용하는 BFS를 참조하시길 바랍니다.

BFS 는 다음과 같은 문제에 사용되는 알고리즘입니다.

1. 최소 상태의 개수가 충분히 작다.

2. 최소비용을 구하는 문제

3. 이동간극(비용)이 1로 동일해야 한다.

위의 조건을 충족하므로 BFS를 사용하여 구하는 것이 수월합니다.

소수인지 판별하는 알고리즘을 생각해보겠습니다.

소수는 자기 자신과 1만으로 나누어 떨어지는 숫자입니다.

자기자신이 N이고 임의의 수가 K일 때 N%K = 0를 만족하는 K가 N과 1밖에 없습니다.

간단하게 코드로 표현하면 다음과 같습니다.

int primeNum(int n)
{
    int count = 0;
    for(int i = 1; i <= n; i++)
    {
        if(n%i == 0)
        {
            count++;
        }
    }
 
 
    return count;
}

count가 2일 때, n은 소수임을 알 수 있습니다.

하지만 일반적으로 소수를 구하는 알고리즘은 에라토스테네스의 알고리즘을 이용합니다. (성능이 더 좋다고 말합니다.)

for(int i = 2; i < 10000; i++)
    {
        if (prime[i] == 0)
        {
            for(int j = i*i; j<10000; j+=i)
            {
                prime[j] == 1;
            }
        }
    }

간단히 설명하면, 2의 배수, 3의 배수, 4의 배수... 를 true(1)처리하고 배열에서 false(0)인 자리가 소수임을 알 수 있습니다.

하지만 이 문제에서는 계산시간이 충분하므로 primeNum()함수를 통해 매 숫자가 소수인지 아닌지를 판별해주는 방식으로 풀었습니다. (에라토스테네스 알고리즘을 통해 미리 소수를 구해놓은 다음 배열의 true 값과 false값으로 판별해주는 방식을 사용해도 상관없습니다)

[풀이과정]

트리형 데이터로 검색하는 과정을 그려보겠습니다.

[그림1] 한번에 한자리 숫자만 변경이 가능하므로 한 데이터에 네 종류의 갈래로 새로운 데이터가 생겨난다.

하나의 데이터에 첫번째 자리의 숫자를 바꿔주고, 두번째 자리의 숫자를 바꿔주고, 세번째 자리의 숫자를 바꿔주고, 네번째 자리의 숫자를 바꿔주면 현재 비밀번호에서 바꿀 수 있는 모든 경우의 수를 확인할 수 있습니다. 이 경우 최소 이동거리를 구하는 문제이므로 사용했던 비밀번호는 제외합니다. (visited 배열을 통해 사용했던 비밀번호는 표시를 해둡니다)

Step 1 : 비밀번호 네자리를 입력받으면 숫자를 바꿔주기 위해서 한자리씩 배열에 저장한다.

Step 2 : while(){

첫번째 숫자를 바꿔주고 소수인지 확인한다 + 사용했던 비밀번호인지 확인한다.

두번째 숫자를 바꿔주고 ...

세번째 숫자를 바꿔주고 ...

네번째 숫자를 바꿔주고 ...

Step 3 : 조건에 만족하면 queue에 비밀번호를 추가하고(q.push) 위 과정을 반복한다.

[정답]

#include<iostream>
#include<queue>
#include<cstdio>
 
using namespace std;
 
int result = -1;    //가능하지 않은 경우는 Impossible을 출력해야하므로 초기값을 부여한다.
 
 
int primeNum(int n)
{
    int count = 0;
    for(int i = 1; i <= n; i++)
    {
        if(n%i == 0)
        {
            count++;
        }
    }
 
 
    return count;
}
 
int square(int a, int n)
{
    int result = 1;
    for(int i = 0; i < n; i++)
    {
        result = result * a;
    }
    return result;
}
 
int bfs(int n, int m)
{
 
    queue<int> q;
    int digit[4];                //네자리 숫자를 저장하는 배열
    int visited[10000] = {0};    //사용했던 비밀번호를 표시하기 위한 배열
    int time[10000] = {0};        //사용하고자 하는 비밀번호를 사용하기까지 얼마나 많은 변경을 했는지 1씩 쌓으면서 확인한다.
 
    int temp;                    //digit배열을 만들기 위한 임시변수
    int now;
    int next_now;
 
 
    visited[n] = 1;
    q.push(n);
 
    while(!q.empty())
    {
        now = q.front();
        q.pop();
 
        if(now == m)                    //찾고자 하는 비밀번호 일 때 반복문을 멈추고 result에 값 대입 (정답부분)
        {
            result = time[m];
            break;
        }
 
        //printf("%d \n", now);
 
        temp = now;
        for(int i = 0; i<4; i++)        //digit 배열에 자릿수 하나씩 나눠서 넣는다
        {
            digit[i] = temp%10;
            temp /= 10;
        }
 
 
        for(int i = 0; i<4; i++)
        {
            for(int j = 0; j<10; j++)
            {
 
                next_now = 0;                //next_now값은 digit값을 계속 더해서 만들어지므로 초기화 해주자
                digit[i] = digit[i]+1 > 9 ? 0 : digit[i]+1;        //현재 자릿수에서 1씩 더하면서 숫자를 바꾼다. 10일 때는 0
 
 
                for(int k = 0; k<4; k++)    //나눠져있는 자릿수를 다시 네자리 숫자로 변경
                {
                    next_now += digit[k]*square(10,k);
 
                }
 
                if(next_now > 1000 && visited[next_now] == 0 && primeNum(next_now) == 2)    //next_now>1000를 통해 맨 앞 0이 숫자들은 자동으로 걸러진다, 방문하지 않은 수 + 소수일 때만 q.push()
                {
                    q.push(next_now);
                    visited[next_now] = 1;
                    time[next_now] = time[now] + 1;
                }
 
            }
        }
 
    }
    return result;
}
 
 
int main()
{
    int N,M;
    int c;
    scanf("%d", &c);
    while(c--)
    {
 
        scanf("%d", &N);
        scanf("%d", &M);
        bfs(N,M);
        if(result == -1)
        {
            printf("Impossible \n");
        }
        else
        {
            printf("%d \n", result);
        }
        result = -1;
 
    }
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다 

1. 백준 정답에는 에라토스테네스 알고리즘을 이용해서 풀었다. 그리고 숫자를 바꿔주는 부분을 내 코드보다 훨씬 더 간결하게 사용했는데

숫자를 string으로 받아온 후(to_string()) string[i]에 다른 숫자들을 대입해 넣었다. 하지만 digit이 다음 대입할 숫자일 때, 

string s = to_string(num); s[index] = digit + '0'; 에서 

'0'을 붙여야하는 이유를 모르겠다. (실제로 '0'을 빼고 출력해보면 null 값이 들어가 있는데 이유를 모르겠다.)

해결: s[index]는 string, digit은 int형이다. 즉 자료형이 다르기 때문에 대입이 이뤄질 수 없다. 하지만 string+int = string을 이용해서 digit을 교묘하게 string으로 바꾼것이다. 참고로 char + int = int 이다(char은 문자 하나만을 넣을 수 있고 문자 하나는 아스키 코드를 의미하기도 하기 때문)

2. 초기화는 반복문 맨 처음에 쓰자.