[백준 / BOJ] C++ 1963 소수 경로

1963번: 소수 경로

 

문제

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

1963번: 소수 경로

 

 

풀이

4자리 소수 A, B를 입력받고 A를 적절히 바꾸어 B를 만드는데 몇 번 만에 바꿀 수 있는지 구하는 문제다. 바꾸는 데는 규칙이 있다.

1. 한 번에 한 자리 수만 바꿀 수 있다.

2. 바뀐 수도 반드시 소수여야 한다.

 

소수인지 판단하기 위해 에라토스테네스의 체를 사용해 소수를 걸러준다. 그리고 bfs를 돌렸다. A를 방문처리하고 큐에 넣는다. 이때 큐는 pair를 원소로 문자열인 수와 몇 번째 바꾼 수인지 cnt를 가진다. 각 자릿수를 변경해 가며 소수이면서 아직 방문하지 않은 모든 경우에 대해 방문처리하고 그 수와 cnt+1을 큐에 추가해 준다. 위 작업을 반복하다가 B와 같은 수가 나오면 ans에 cnt를 대입해 준다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int ans;
string a, b;
vector<int> sieve(10001, 1), visited(10001, 0);

void bfs() {
  ans = -1;
  queue<pair<string, int>> q;
  q.push({a, 1});
  visited[stoi(a)] = 1;
  while (!q.empty()) {
    string s = q.front().first;
    int cnt = q.front().second;
    q.pop();
    for (int i = 0; i < 4; i++) {
      char tmp = s[i];
      for (int j = 0; j < 10; j++) {
        s[i] = j + '0';
        int n = stoi(s);
        if (n >= 1000 && sieve[n] && !visited[n]) {
          if (s == b) {
            ans = cnt;
            return;
          }
          q.push({s, cnt + 1});
          visited[n] = 1;
        }
      }
      s[i] = tmp;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 2; i <= 10000; i++)
    if (sieve[i])
      for (int j = i * 2; j <= 10000; j += i)
        sieve[j] = 0;
  int t;
  cin >> t;
  while (t--) {
    cin >> a >> b;
    if (a == b) {
      cout << "0\n";
      continue;
    }
    for (int i = 1000; i <= 9999; i++)
      visited[i] = 0;
    bfs();
    if (ans == -1)
      cout << "Impossible\n";
    else
      cout << ans << '\n';
  }
  return 0;
}