[BOJ] 1963번 - 소수 경로

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

요즘 왜인지 무기력해서 문제 푸는게 힘들었는데 오랜만에 새로운 문제를 풀었다.

물론 쉬운 문제여서지만 첫 시도에 AC를 받으니 기분이 좋다.

 

제일 먼저 에라토스테네스의 체를 통해 네 자리수 소수를 모두 표시했다.

또한 비밀번호는 한 번에 한 자리만 변경할 수 있으므로 단계마다 최대 $9^4$가지의 경우의 수가 있는데,

그 경우의 수를 쉽게 구하기 위해 string을 이용했다. 

현재 비밀번호를 string 변수에 담은 후, 각 인덱스마다 0부터 9까지의 수로 바꿔 조건을 만족하는지 확인하였다.

여기서 조건이란 '4자리 수 && 소수 && 방문하지 않은 수'를 말한다.

 

그 외에는 전형적인 bfs 문제였다.

 

/*
20200517
baekjoon 1963번 - 소수 경로
*/
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <cmath>
using namespace std;

int prime[10000]; bool visited[10000]; int ans; bool found = false;
void notePrime() {
	//처음에 다 소수로 가정
	fill(prime, prime + 10000, 1);

	//에라토스테네스의 체
	for (int i = 2; i*i <= 9999; ++i) {
		if (prime[i]) {
			int tmp = 2;
			while (i*tmp <= 9999) {
				prime[i*tmp++] = 0;
			}
		}
	}
}

//조건 만족하는지 확인(4자리수 && 소수 && 아직 방문 안함)
bool isRange(string n) {
	int num = atoi(n.c_str());
	return num >= 1000 && num <= 9999 && prime[num] && !visited[num];
}

void bfs(int start, int end) {
	queue<int>q;
	visited[start] = 1;
	q.push(start);

	while (!q.empty()) {
		int sz = q.size();
		while (sz--) {
			int cur = q.front();
			q.pop();
			//최종 목적지 도달한 경우 bfs 종료
			if (cur == end) {
				found = true;
				break;
			}
			string num = to_string(cur);
			for (int i = 0; i < 4; ++i) {
				string tmp = num;
				for (int j = 0; j <= 9; ++j) {
					tmp[i] = j + '0';
					if (isRange(tmp)) {
						visited[atoi(tmp.c_str())] = 1;
						q.push(atoi(tmp.c_str()));
					}
				}
			}
		}
		if (found)break;
		ans++;
	}
}

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	notePrime();
	while (t--) {
		int n1, n2;
		cin >> n1 >> n2;

		memset(visited, 0, sizeof(visited));
		ans = 0; found = false;
		bfs(n1, n2);
		if (found) {
			cout << ans << "\n";
		}
		else {
			cout << "Impossible\n";
		}
	}
}