1963번

1963번 - 소수 경로

문제를 보는 순간 '소수' -> 2가지 방법 ( 1. 에라토스테네스의 채. 2.루트N까지 for문으로 나눠보기)

그리고 숫자들을 정점이라고 했을 때, 변할 때 가중치가 따로 없으므로 1이라고 한다면 

최단 거리를 구하기 떄문에 BFS로 풀 수 있다.

그래서 처음에 에라토스테네스의 채를 이용해서 N의 범위인 9999까지 소수를 모두 구해놓는다.

그리고 시작점을 BFS의 시작점으로 놓고, 각 자리의 수를 변화시킨다. 그때 변화된 점이 방문한 적이 없고, 소수이면 큐에 집어 넣는다.

목표로 하는 값이 나오면 while 문을 나오고 dist값을 반환해준다.

단, 내가 처음에 빠졌던 함정은

네자리 숫자이기 때문에 맨 앞에만 0이 올 수 없다는 점.

<정답 코드>

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
 
bool del[10000];
bool primeNum[10000];
 
void getPrime()
{
    for (int i = 2; i <= 9999; i++)
    {
        if (!del[i])
        {
            primeNum[i] = true;
            for (int j = i * i; j <= 9999; j += i)
            {
                del[j] = true;
            }
        }
    }
 
}
int main()
{
    int tc;
    cin >> tc;
    getPrime();
 
    for (int t = 1; t <= tc; t++)
    {
        int start, dest;
        bool visited[10000];
        int dist[10000];
        
        memset(visited, false, sizeof(visited));
        memset(dist, -1, sizeof(dist));
 
        cin >> start >> dest;
 
        queue<int> q;
        q.push(start);
        visited[start] = true;
        dist[start] = 0;
 
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
 
            if (now == dest)
            {
                break;
            }
 
            int first = now / 1000;
            int second = (now % 1000) / 100;
            int third = (now % 100) / 10;
            int fourth = now % 10;
 
            for (int i = 0; i <= 9; i++)
            {
                if (i != first && i!=0)
                {
                    int next = now - (1000 * first) + (1000 * i);
                    if (!visited[next] && primeNum[next])
                    {
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }
                }
 
                if (i != second)
                {
                    int next = now - (100 * second) + (100 * i);
                    if (!visited[next] && primeNum[next])
                    {
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }
 
                }
 
                if (i != third)
                {
                    int next = now - (10 * third) + (10 * i);
                    if (!visited[next] && primeNum[next])
                    {
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }
                }
 
                if (i != fourth)
                {
                    int next = now - (fourth) + (i);
                    if (!visited[next] && primeNum[next])
                    {
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }
                }
            }
 
        }
 
        if (dist[dest] == -1)
        {
            cout << "Impossible" << endl;
        }
        else
        {
            cout << dist[dest] << endl;
        }
 
    }
 
 
    return 0;
}