백준 2023번 [신기한 소수]

인접 리스트를 미리 받아놓지 않고 재귀 함수를 돌리면서 다음 깊이를 찾아가는 DFS

같은 조건으로 크기를 키워갈 때 사용 고려

int n;

bool isPrime(int num) {
	for (int i = 2; i <= num / 2; i++) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}

void DFS(int num, int jarisu) {
	if (jarisu == n) {
		if (isPrime(num)) {
			cout << num << "\n";
		}
		return;
	}
	for (int i = 1; i < 10; i += 2) {
		if (isPrime(num)) {
			DFS(num * 10 + i, jarisu + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	DFS(2, 1);
	DFS(3, 1);
	DFS(5, 1);
	DFS(7, 1);

	return 0;
}