BOJ #1963. 소수 경로 (Gold 하위권)

오랜만에 수학 문제가 풀고 싶어졌습니다. 그렇다고 막 IQ 문제 풀고 싶은게 아니라, 적절한 도구를 이용해서 해결할 수 있는 문제를 풀고 싶었어요. 그래서 에라토스테네스 문제나, 유클리드 호제법 문제를 풀려고 solved에서 고르던 중 발견한 좋은 문제입니다~

www.acmicpc.net/problem/1963

1963번: 소수 경로

딱 봐도 '소수' 가 붙어있으니, 에라토스테네스의 체 (sieve) 문제일 거 같다는 생각이 들지 않나요?

다행히 예상을 빗나가지 않았습니다!

---

의식의 흐름.

도대체 저 한 자리를 어떤 기준으로 바꿀까? 

목표 소수에 가까운 자릿수로 바꿔야되나?

일단, 나중에 생각하고 10000까지 에라토스테네스 체로 소수들을 구해놓자. 

다 구해놨고, 이제 수를 어떻게 변환하지? 최소의 횟수로 변환해야된다... (이것저것 막 하면서 10분 정도 고민)

DP인가? 아니야, 시작 소수에 따라 특정 소수까지의 변환 횟수가 달라지니까, dp라 할 수 없어.

잠깐만, 최단경로? A->B 문제(#16953)나, 숨바꼭질 문제(#12851)처럼 bfs를 이용하면 되겠구나~

각 자리 숫자를 바꿔주는 과정은 수로 처리하려면 1000을 더하고 100을 더하고 막 이래야될테니 불편하겠네. string으로 바꿔서 해결하자.

---

해결 방법.

1. 각 테스트 케이스가 있으니, 각 테케마다 visit 초기화를 해주어야 한다.
2. BFS로 queue에 넣어줄 인자로는 변환 횟수, 변환된 소수 이다. 변환된 소수가 최종 소수일 경우 변환 횟수를 return해준다.
3. 각 자리 수를 하나씩만 바꿔줄 땐, 첫째 자리는 0으로 바꿔줄 수 없으니 for문으로 1~9까지 돌아 그 자리 문자를 i+'0'으로 바꿔준다. (string으로 진행)
4. 둘째, 셋째, 넷째 자리는 0으로도 바꿔줄 수 있으니 for문으로 0~9까지 돈다.
5. 조건에 만족할 경우 queue에 삽입해서 bfs처럼 해결한다. 만약, while문 안에서 return이 안됐을 경우, 불가능한 경우이므로 -1을 return해줘 impossible을 띄워주게 한다.

---

주의사항.

1. 각 테케마다 visit을 초기화해주지 않으면, 두번째 테스트케이스의 답이 Impossible로 뜰 수 있다.

---

소스 코드.

// 210123 #1963 소수 경로 Gold V
// sieve (소수) + bfs (최단경로)
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int MAX = 10001;
bool prime[MAX], visit[MAX];
// sieve O(log(10000))
void sieve() {
	fill(prime, prime + MAX, true);
	for (int i = 2; i * i < 10000; i++) {
		if (!prime[i])
			continue;
		for (int j = i * 2; j < 10000; j += i) {
			prime[j] = false;
		}
	}
}
// bfs to get minimum distance road
int bfs(string n, string b) {
	queue<pair<int, string>> q;
	q.push({ 0, n });
	visit[stoi(n)] = true;
	while (!q.empty()) {
		string x = q.front().second;
		int time = q.front().first;
		q.pop();
		if (x == b)
			return time;
		// change string
		string s = x;
		// first digit
		for (int i = 1; i < 10; i++) {
			// string
			if (s[0] != i+'0') {
				// change first digit
				s[0] = i + '0';
				// not visit && prime
				if (!visit[stoi(s)] && prime[stoi(s)]) {
					visit[stoi(s)] = true;
					q.push({ time + 1, s });
				}
			}
		}
		// second digit, third digit, fourth digit
		for (int j = 1; j <= 3; j++) {
			string s = x;
			for (int i = 0; i < 10; i++) {
				if (s[j] != i + '0') {
					// change digit
					s[j] = i + '0';
					if (!visit[stoi(s)] && prime[stoi(s)]) {
						visit[stoi(s)] = true;
						q.push({ time + 1, s });
					}
				}
			}
		}
	}
	// Impossible: -1
	return -1;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	sieve();
	while (t--) {
		fill(visit, visit + MAX, false);
		int a, b;
		cin >> a >> b;
		// change string because change the digit easier
		int ans = bfs(to_string(a), to_string(b));
		if (ans == -1) {
			cout << "Impossible\n";
		}
		else
			cout << ans << "\n";
	}
}

영어를 못해서 github에 올릴 코드 주석이 좀 이상할 수 있어요 ㅎㅎ...

요즘 github desktop으로 한글 코드를 올리면 한글이 깨지더라구요 ㅠㅠ

 

조언 및 피드백 환영입니다!