글 읽기 - 제가 시간복잡도를 제대로 계산한건가요?

yobs0814 5년 전 0

BFS 시간복잡도가 ( 정점 + 간선)의 개수로 알고 있는데요.

정점의 개수를 1000~9999 사이의 소수의 개수로 두었고,

간선은 각 정점에 대해서 (각각의 자리수를 바꿔보는 것)

천의 자리의 경우 1~9

백의 자리, 십의 자리, 일의 자리의 경우 0~9라고 두어서

간선의 개수를 약 10개라고 두었습니다.

그 결과

( 정점(1000~9999 사이의 소수의 개수) + 간선(10) )로 생각을 했는데

이렇게 계산하는것이 맞는지~ 궁금합니다.

void BFS(int start, int end) {
	queue<int>qu;
	qu.push(start);
	dist[start] = 0;

	while (!qu.empty()) {
		int temp = qu.front(); qu.pop();

		if (temp == end) {
			done = true;
			ans = dist[end];
			break;
		}

		//천의 자리
		int temp2 = temp;
		temp2 = temp2 - (temp2 / 1000) * 1000;

		for (int i = 1; i < 10; i++) {

			temp2 += i * 1000;
			if (!prime[temp2] && dist[temp2] < 0) {
				dist[temp2] = dist[temp]+1;
				qu.push(temp2);
			}
			temp2 -= i * 1000;
		}
		//백의 자리
		temp2 = temp;
		temp2 -= ((temp2 % 1000) / 100) * 100;

		for (int i = 0; i < 10; i++) {

			temp2 += i * 100;

			if (!prime[temp2] && dist[temp2] < 0) {
				dist[temp2] = dist[temp] + 1;
				qu.push(temp2);
			}
			temp2 -= i * 100;
		}
		//십의 자리
		temp2 = temp;
		temp2 -= ((temp2 % 100) / 10) * 10;

		for (int i = 0; i < 10; i++) {

			temp2 += i * 10;

			if (!prime[temp2] && dist[temp2] < 0) {
				dist[temp2] = dist[temp] + 1;
				qu.push(temp2);
			}
			temp2 -= i * 10;
		}
		//일의 자리
		temp2 = temp;
		temp2 -= temp2 % 10;

		for (int i = 0; i < 10; i++) {

			temp2 += i;

			if (!prime[temp2] && dist[temp2] < 0) {
				dist[temp2] = dist[temp] + 1;
				qu.push(temp2);
			}
			temp2 -= i;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 시간복잡도를 제대로 계산한건가요?

yobs0814 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말