글 읽기 - 숨바꼭질 4 메모리초과 c++

dopppp 2년 전 0

bfs를 이용해서 코드를 짜보았습니다.

최대한 간결하고 배열도 많이 안 쓰는 방향으로 짜려고 노력했는데 메모리 초과가 뜨네요..

이 코드에서 메모리 초과가 나는 이유가 무엇인지 정말 정말 궁굼합니다 ㅠㅠ

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
queue <int> Q;
vector <int> route;
int r[100001];
int main(){
	memset(r,-1,sizeof(r));
	int i,n,k,p;
	cin>>n>>k;
	Q.push(n);
	r[n]=-2;
	while(!Q.empty()){
		int x=Q.front();
		if(x==k)break;
		Q.pop();
		if(x<=50000&&r[x*2]==-1){r[x*2]=x;Q.push(x*2);}
		if(x<100000&&r[x+1]==-1){r[x+1]=x;Q.push(x+1);}
		if(x>=1&&r[x-1]==-1){r[x-1]=x;Q.push(x-1);}
	}
	for(p=k;r[p]!=-2;p=r[p])route.push_back(p);
	cout<<route.size()<<"\n"<<n<<" ";
	for(i=route.size()-1;i>=0;i--)cout<<route[i]<<" ";
}

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

문제

문제

출처

ICPC

숨바꼭질 4 메모리초과 c++

dopppp 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말