글 읽기 - 1697 반례찾는데 도움 주시면 정말 감사하겠습니다.

qocn9029 4년 전 0

제 생각에는 dis배열의 범위설정과 관련해서 틀렷거나 아니면 제 코드 로직 어딘가 잘못돼있는거 같은데 저는 해결하지 못하고 있습니다.

제가 입력한 테스트케이스는 원하는 결과가 나오는데 아직 틀린 케이스를 못 찾고 있습니다.

한번 봐주시면 감사하겠습니다.

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cnt=0;//최종 구하려는 답
bool check[100001];
int dis[100001]; //-->답을 내는 방식

void BFS(int n,int k){//n은 시작노드 k는 목적지노드
	queue<int> q;
	check[n]=true;
	q.push(n);

	while(!q.empty()){//bfs는 큐에서 나오는 순서가 방문 순서가 아님!

		int next=q.front();

		q.pop();

		if(next==k){
			cnt=dis[next];
			break;
		}

		if(check[next-1]==false && next-1<=100000 && next-1>=1){
			check[next-1]=true;
			q.push(next-1);
			dis[next-1]=dis[next]+1;
		}

		if(check[next+1]==false && next+1<=100000 && next+1>=1){
			check[next+1]=true;
			q.push(next+1);
			dis[next+1]=dis[next]+1;
		}

		if(check[2*next]==false && 2*next<=100000 && 2*next>=1){
			check[2*next]=true;
			q.push(2*next);
			dis[2*next]=dis[next]+1;
		}
	}

	return ;
}

int main(){
	int n;
	int k;
	cin>>n>>k;

	fill(check,check+100001,false);
	fill(dis,dis+100001,0);

	BFS(n,k);

	cout<<cnt<<endl;
}

ha_ram 4년 전 1

27, 33, 39번째 줄의 if문에서 check[next-1], check[next+1], check[2*next] 조건을 먼저 조사하면 안됩니다.

next-1과 next+1과 2*next가 check범위를 벗어날 수 있기 때문에 check[next-1], check[next+1], check[2*next]를 먼저 조사하면 안되고

if(next-1<=100000 && next-1>=1 && check[next-1]==false)

if(next+1<=100000 && next+1>=1 && check[next+1]==false)

if(2*next<=100000 && 2*next>=1 && check[2*next]==false)

이렇게 범위 내에 들어오는지 먼저 조사하게 해야 합니다.

wjddydgns99 4년 전 0

N(0 ≤ N ≤ 100,000) 이면 next-1, next+1, 2*next 들이 >=1 이 아니라 >=0 아닌가요? (자세히 보진 않아서...)

예를들어, 4 0 이 입력되면 못갈 것 같습니다만..

qocn9029 4년 전 0

인덱스를 1로 시작하는 버릇때문에 문제를 잘못이해했었네요 감사합니다!

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

문제

문제

출처

ICPC

1697 반례찾는데 도움 주시면 정말 감사하겠습니다.

qocn9029 4년 전 0

ha_ram 4년 전 1

wjddydgns99 4년 전 0

qocn9029 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말