글 읽기 - bfs 반레.....

hhkim593 5년 전 0

두개의 큐를 이용하며, 거리배열을 -1로 초기화시켜 -1이 발견 될때마다 탐색하는 bfs구현소스 입니다. 문제에서 제시되는 입력을 넣으면 올바른 값이 출력되는데 제출하면 틀렸다고 나옵니다. 반례를 찾으려 해봐도 원하는 답이 나와서 어느 부분이 잘못됬는지 잘 모르겠습니다 ㅜㅜㅜ... 어디가 문제일까요 ??

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int d[100000];
const int MAX = 100000;
int n, m;
int main() {
	cin >> n >> m;
	queue<int>q;
	queue<int>next_q;
	memset(d, -1, sizeof(d));
	d[n] = 0;
	q.push(n);

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (2 * x < MAX && d[2 * x] == -1) {
			q.push(2 * x);
			d[2 * x] = d[x];
		}

		if (x - 1 >= 0 && d[x - 1] == -1) {
			d[x - 1] = d[x] + 1;
			next_q.push(x - 1);
		}
		if (x + 1 < MAX && d[x + 1] == -1) {
			d[x + 1] = d[x] + 1;
			next_q.push(x + 1);
		}
		if (q.empty()) {
			q = next_q;
			next_q = queue<int>();
		}
	}
	if (d[m] != -1) {
		cout << d[m];
	}
	return 0;
}

hello70825 5년 전 1

https://ideone.com/xq0nwJ

답은 0인데 아무것도 출력을 안하고 있습니다.

hhkim593 5년 전 0

아 덕분에 max상수랑 배열크기를 10배 더 확장했어야함을 알게됬습니다 감사합니다!!!

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

문제

문제

출처

ICPC

bfs 반레.....

hhkim593 5년 전 0

hello70825 5년 전 1

hhkim593 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말