글 읽기 - 변환하려는 소수를 찾았을 때 바로 break하면 안되는 이유

seungwonoh57 6년 전 0

while문 안에서 큐가 빌 때까지 계속 도는데

큐를 팝해서 변환하려는 소수를 찾았을 때 바로 break해서 while문 탈출하면

틀렸다고 나오는데

그걸 지우면 바로 정답이 나옵니다.

이유가 궁금합니다.

#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

void eratosthenes(bool *prime){
	for(int i = 2; i <= 10000; i++){
		if(prime[i] == false){
			for(int j = i * i; j <= 10000; j += i){
				prime[j] = true;
			}
		}
	}
	
	for(int i = 2; i <= 10000; i++){
		prime[i] = !prime[i];
	}
}

int change(int from, int place, int num){
	
	// library 가능 시
	string s = to_string(from);
	s[place] = '0' + num;
	return stoi(s);
	
}

int main(){
	
	int T, from, to;
	bool ans_found = false;
	bool check[10001];
	int dist[10001];
	bool prime[10001];
	queue <int> q;
	
	eratosthenes(prime);

	cin >> T;
	
	for(int test_case = 1; test_case <= T; test_case++){
		cin >> from >> to;
		memset(check, false, sizeof(check));
		memset(dist, 0, sizeof(dist));
		
		check[from] = true;
		// dist[from] = 0;
		q.push(from);
		
		while(!q.empty()){ // 10000
			int current = q.front();
			q.pop();
			
			
			for(int place = 0; place <= 3; place++){ // i번째 자리 변형 (4321)
				for(int num = 0; num <= 9; num++){ // i번쨰 자리에 바꿀 숫자
					
					// 반드시 네 자리 수여야 하므로 맨 앞자리 0으로 바꾸면 안됨
					if(place == 0 && num == 0){
						continue;
					}
		 
					int next = change(current, place, num); // 수 변형
					
					// 바꾼 수가 소수이면서 처음 발생한 경우의 수이라면, 큐에 추가
					if(prime[next] == true && check[next] == false){
						check[next] = true;
						q.push(next);
						dist[next] = dist[current] + 1;
					}
					
				}
			}
		}
		
		cout << dist[to] << endl;
		 
	}
	
	return 0;
}

kdk8361 6년 전 0

바로 브레이크를 걸면 큐에 값이 남아있게 됩니다. 그게 다음 테케에 영향을 줘서 그렇다고 생각합니다.

kensyrow 6년 전 1

첫번째 예시를 보면 1033 -> 1733 -> 3733 .. 순으로 가죠?

그런데 1033 에서 100의 자리를 바꿔가며 소수를 탐색하면 1433, 1733, 1933 이렇게 3가지 경우가 더 있습니다.

만약 1433을 찾자마자 바로 break를 하게되면, 1733은 queue에 들어가지 못하고 정답을 찾을 수 없게 됩니다.

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

문제

문제

출처

ICPC

변환하려는 소수를 찾았을 때 바로 break하면 안되는 이유

seungwonoh57 6년 전 0

kdk8361 6년 전 0

kensyrow 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말