글 읽기 - bfs로 했는데 메모리 초과가 납니다..

seungwonoh57 6년 전 0

메모리 초과가 바로 나는데 일단 bfs로 풀어도 되는지가 궁금합니다.

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

int main(){
	
	int F, S, G, U, D;
	scanf("%d %d %d %d %d", &F, &S, &G, &U, &D);
	
	queue <int> q;
	vector <bool> check(F+1);
	vector <int> dist(F+1);
	bool found = false;
	
	
	q.push(S);
	check[S] = true;
	dist[S] = 0;
	
	// 정렬될 때까지 완전 탐색
	while(!q.empty()){
		int cur = q.front(); // 현재 카드 덱
		q.pop();
		
		
		if(cur == G){
			found = true;
			break;
		}
		
		if(cur + U <= 1000000){
			q.push(cur+U);
			check[cur+U] = true;
			dist[cur+U] = dist[cur] + 1;
		}
		
		if(cur-D >= 1){
			q.push(cur-D);
			check[cur-D] = true;
			dist[cur-D] = dist[cur] + 1;
		}
	}
	
	if(found){
		cout << dist[G] << endl;
	}
	else{
		cout << "use the stairs" << endl;
	}

	return 0;
}

djm03178 6년 전 0

check 를 만들어놓고 사용을 안 하셔서, 같은 층을 계속 재방문하기 때문에 초과합니다.

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

문제

문제

출처

ICPC

bfs로 했는데 메모리 초과가 납니다..

seungwonoh57 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말