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

dfs를 활용해서 푼 완전탐색 문제이다 

 

#접근방법

먼저 소수인지 아닌지 판별하기 위해서 에네토스테라스의 체 방식으로 체크를 해줬다. 

(소수가 아닌 것들은 모두 true로 설정하였다. )

 

먼저 queue에다가 시작 숫자 4자리와 count 값을 넣어준다. 

그리고 숫자 4자리 수에 각 자릿수 마다 0부터 9까지 넣어서 소수이면서 범위 내에 있고 방문하지 않았다면 dfs를 호출한다. 만약 세가지 조건에 하나라도 포함되어있다면 continue 를 해준다. 

 

이후 찾고자 하는 숫자와 같다면 count값을 출력해주고 만약 찾고자 하는 값이 없다면 "Impossible"을 출력해주자. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <tuple>
using namespace std; 
int n;
bool check[10001];
bool visited[10001]; 
string s1, s2; 
void init() {
	for (int i = 2; i < 10000; i++ ) {		
		if (check[i] == false) {
			for (int j = i * 2; j < 10000; j += i) {
				check[j] = true; 
			}
		}
	}
}
void dfs() {
	queue <pair<string, int>>q;
	visited[stoi(s1)] = true;
	q.push({ s1, 0 });
	while (!q.empty()) {
		string s; 
		int cnt; 
		tie(s, cnt) = q.front(); 
		q.pop(); 
		if (s == s2) {
			cout << cnt << endl; 
			return; 
		}		 
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j <= 9; j++) {
				string ss = s; 
				ss[i] = j + '0'; 
				if (check[stoi(ss)] == true)continue; //소수아님
				if (visited[stoi(ss)] == true)continue; 
				if (stoi(ss) < 1000 )continue;
				visited[stoi(ss)] = true; 
				q.push({ss, cnt+1 }); 
			}
		}
	}	
	cout << "Impossible" << endl;
}
int main() {
	cin >> n;
	init(); 
	while (n--) {
		cin >> s1 >> s2;
		dfs(); 	
		memset(visited, false, sizeof(visited)); 
	}
}

1963번: 소수 경로