글 읽기 - bfs활용시

maro7913 4년 전 0

안녕하세요.

문제 풀이 중 이해가 안되는 부분이 있어서 문의 드립니다.

bfs를 사용했는데, whil(!q.empty())다음에

q의 크기 만큼 for문을 돌리려고 했습니다.

그래서

for(i=0; i<q.size();i++)

라고 하니깐 틀린 값이 나오고

int s= q.size()로 하니깐 제대로 된 값이 나옵니다.

왜그럴까요?

#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
vector<int> prime(2);
vector<int>num,chk;
int cnt;
void Prime() {
num = vector<int>(10000, 1);
		for (int i = 2; i <= sqrt(9999); i++) {
			if (num[i] == 0) continue;
			for (int j = i * 2; j <= 9999; j += i) {
				num[j] = 0;
			}
		}
}
void bfs() {
	queue<int> q;
	chk = vector<int>(10000, 0);
	q.push(prime[0]);
		while (!q.empty()) {
			int s = q.size();//이부분
			for (int i = 0; i <s; ++i) {
				
				int cur = q.front(); q.pop();
				chk[cur] = 1;

				if (cur == prime[1]) { 
					return; 
				}
				string str1 = to_string(cur);
				for (int a = 0; a < 4; ++a) {
					string tmp = string(str1);
					for (int b = 0; b < 10; ++b) {
						tmp[a] = b+48 ;
						int inte = stoi(tmp);
						if (num[inte] && inte>=1000 && !chk[inte]) {
							chk[inte] = 1;
							q.push(inte);
						}
					}
				}
			}
			cnt++;
		}
		cout << "Impossible" << endl;
		return;
}
int main() {
	int T;
	cin >> T;
	Prime();
	for (int t = 0; t < T; t++) {
		cin >> prime[0] >> prime[1];
		cnt = 0;
		bfs();
		cout << cnt<<endl;
	}//end for test case

	return 0;
}

3587jjh 4년 전 1

q.size()는 계속 바뀌니까요

maro7913 4년 전 0

아....

멍청한 질문이었네요....

감사합니다!!ㅠㅠ

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

문제

문제

출처

ICPC

bfs활용시

maro7913 4년 전 0

3587jjh 4년 전 1

maro7913 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말