취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17394번 문제인 핑거 스냅이다.
문제는 아래 링크를 확인하자.

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

BFS를 이용하여 가장 빠르게 목적이 되는 수까지 도달하는 횟수를 세자.

각 숫자에 도달할 때마다 "A이상 B이하 && 이 숫자는 소수" 라는 조건을 만족하는지를 체크하면 된다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

bool sieve[1000001];
int visited[1000001];

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

	sieve[0] = sieve[1] = 1;

	for (int i = 2; i < 317; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j <= 1000000; j += i) {
			sieve[j] = 1;
		}
	}

	int T; cin >> T;
	while (T--) {
		memset(visited, 0, sizeof(visited));
		queue<int> que;
		int N, A, B; cin >> N >> A >> B;
		que.push(N);
		visited[N] = 1;
		int ans = -1;
		while (!que.empty()) {
			int current = que.front(); que.pop();
			if (A <= current && current <= B && !sieve[current]) {
				ans = visited[current] - 1;
				break;
			}
			if (!visited[current / 2]) {
				visited[current / 2] = visited[current] + 1;
				que.push(current / 2);
			}
			if (!visited[current / 3]) {
				visited[current / 3] = visited[current] + 1;
				que.push(current / 3);
			}
			if (current > 0) {
				if (!visited[current - 1]) {
					visited[current - 1] = visited[current] + 1;
					que.push(current - 1);
				}
			}
			if (current < 100000) {
				if (!visited[current + 1]) {
					visited[current + 1] = visited[current] + 1;
					que.push(current + 1);
				}
			}
		}
		cout << ans << '\n';
	}
}