글 읽기 - c++) BFS로 푸는데 반례, 틀린점 알려주세요

alpha_plus 2년 전 0

일부 케이스 (예시 케이스 등) 에서는 정답이 나오지만, 정작 채점에선 틀렸다고 나옵니다. 반례 없을까요? 그리고 틀린 이유를 아신다면 설명해 주실 수 있나요?

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<queue>
int n, k;
using namespace std;
int check[100100];
int cnt = 0;
void Bfs(int node)
{
	check[node] = 1;
	queue<int> q;
	q.push(node);
	while (!q.empty())
	{
		
		int size = q.size();
		for (int i = 0; i < size; i++)
		{
			int num = q.front();
			q.pop();
			if (num == k)
			{
				return;
			}
			if (check[num + 1] == 0 && num + 1 > 0 && num + 1 < 100000)
			{
				check[num + 1] = 1;
				q.push(num + 1);
			}
			if (check[num - 1] == 0 && num - 1 > 0 && num - 1 < 100000)
			{
				check[num - 1] = 1;
				q.push(num - 1);
			}
			if (check[num * 2] == 0 && num * 2 > 0 && num * 2 < 100000)
			{
				check[num * 2] = 1;
				q.push(num * 2);
			}
			
		}
		
		cnt++;
	}

}
int main()
{
	
	scanf("%d%d", &n, &k);
	Bfs(n);
	printf("%d", cnt);
	return 0;
}

becl3ver 2년 전 0

5 0 넣으면 결과가 안 나오네요

제가 제대로 이해한게 맞다면 동생의 위치는 0 이상 100000 이하인데 초과 미만으로 된거 같아요

alpha_plus 2년 전 0

그렇군요! 한번 수정해 보겠습니다!

alpha_plus 2년 전 0

수정했는데 맞았습니다! 도움주셔서 감사합니다!

becl3ver 2년 전 0

네 다행이네요 ㅎㅎ

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

문제

문제

출처

ICPC

c++) BFS로 푸는데 반례, 틀린점 알려주세요

alpha_plus 2년 전 0

becl3ver 2년 전 0

alpha_plus 2년 전 0

alpha_plus 2년 전 0

becl3ver 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말