글 읽기 - 메모리 초과를 어떻게 하면 해결 할 수 있을까요?

rhdtka21 5년 전 0

윗 코드를 처음 제출했더니 메모리 오버가 떠서 질문글을 읽어봤습니다. https://www.acmicpc.net/board/...

이 글에서 모든 토마토에서 같이 BFS를 해야 된다고 하셔서

새롭게 수정한 코드를 했는데도 메모리 초과가 되네요... 어떻게 해야할까요...

//////////////////////////////////수정 전 코드/////////////////////////////////////////
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int maps[1001][1001];
int check[1001][1001];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};


void BFS(int x, int y){
	queue<pair<int, int> > q;
	q.push(make_pair(x,y));
	check[x][y]=1;
	while(!q.empty()){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		int temp = check[x][y];
		for(int k=0; k<4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(0 <= nx && nx < M && 0 <= ny && ny < N){
				if(maps[nx][ny] == 0 && (check[nx][ny] == 0 || check[nx][ny] >= temp)){
					q.push(make_pair(nx,ny));
					check[nx][ny]=temp+1;
				}
			}
		}
	} 
	
}

int main(void){

	int k=0;
	cin >> N >> M;

	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &maps[i][j]);
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] == -1){
				check[i][j] = -1;
			}
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] ==1){
				BFS(i,j);
			}
		}
	}
	/*
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			cout<<check[i][j]<<'\t';
		}
		cout<<endl;
	}*/
	int max = check[0][0];
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(check[i][j]==0){
				cout<<"-1"<<'\n';
				exit(0);
			}
			else if(check[i][j] > max){
				max = check[i][j];
			}
		}
	}
	cout<<max-1<<'\n';
	return 0;
}
//////////////////////////////////수정 후 코드/////////////////////////////////////////
#include <iostream>
#include <queue>
using namespace std;
int N, M;
int maps[1001][1001];
int check[1001][1001];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

queue<pair<int, int> > q;
void BFS(){
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int temp = check[x][y];
		for(int k=0; k<4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(0 <= nx && nx < M && 0 <= ny && ny < N){
				if(maps[nx][ny] == 0 && (check[nx][ny] == 0 || check[nx][ny] >= temp)){
					q.push(make_pair(nx,ny));
					check[nx][ny]=temp+1;
				}
			}
		}
	} 
	
}

int main(void){

	int k=0;
	cin >> N >> M;

	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &maps[i][j]);
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] == -1){
				check[i][j] = -1;
			}
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] ==1){
				q.push(make_pair(i,j));
				check[i][j]=1;
			}
		}
	}
	BFS();
	/*
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			cout<<check[i][j]<<'\t';
		}
		cout<<endl;
	}*/
	int max = check[0][0];
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(check[i][j]==0){
				cout<<"-1"<<'\n';
				exit(0);
			}
			else if(check[i][j] > max){
				max = check[i][j];
			}
		}
	}
	cout<<max-1<<'\n';
	return 0;
}

rhdtka21 5년 전 0

BFS를 수정했으니 21행 조건이 필요없다 싶어서 지웠더니 통과가 되었네요... 근데 저 조건문 하나로 메모리 오버가 왜 나는건지 궁금합니다 -_-

#include <iostream>
#include <queue>
using namespace std;
int N, M;
int maps[1001][1001];
int check[1001][1001];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

queue<pair<int, int> > q;
void BFS(){
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int temp = check[x][y];
		for(int k=0; k<4; k++){
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(0 <= nx && nx < M && 0 <= ny && ny < N){
				if(maps[nx][ny] == 0 && check[nx][ny] == 0){
					q.push(make_pair(nx,ny));
					check[nx][ny]=temp+1;
				}
			}
		}
	} 
	
}

int main(void){

	int k=0;
	cin >> N >> M;

	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			scanf("%d", &maps[i][j]);
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] == -1){
				check[i][j] = -1;
			}
		}
	}
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(maps[i][j] ==1){
				q.push(make_pair(i,j));
				check[i][j]=1;
			}
		}
	}
	BFS();
	/*
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			cout<<check[i][j]<<'\t';
		}
		cout<<endl;
	}*/
	int max = check[0][0];
	for(int i=0; i<M; i++){
		for(int j=0; j<N; j++){
			if(check[i][j]==0){
				cout<<"-1"<<'\n';
				exit(0);
			}
			else if(check[i][j] > max){
				max = check[i][j];
			}
		}
	}
	cout<<max-1<<'\n';
	return 0;
}

chogahui05 5년 전 0

check[nx][ny] >= temp

가 무슨 의미인지는 잘 모르겠지만. check[nx][ny]는 (nx,ny)에 방문한 시간을 의미할 거고.

temp는 현재 시간 정도를 의미하지 않나 싶습니다.

그런데 문제는. bfs..

일단 메모리 초과 난 코드를 잘 보시면, (i,j)라는 것에 방문했는지 여부에 관계없이 일단 들어가 볼 거란 말입니다.

그러면 최악의 경우에 어떻게 될 거냐면.

0 [1] 0 0 0

1 1 1 0 0

0 1 0 0 0

0 0 0 0 0

이런 식으로 맵이 있다고 했을 때. 일단

0 1 0 0 0

3 2 3 0 0

0 4 0 0 0

0 5 0 0 0

0 6 0 0 0

이렇게 될 거란 말이죠. 그런데 보세요. 그 다음에

0 1 0 0 0

[3] 2 3 0 0

0 4 0 0 0

0 5 0 0 0

0 6 0 0 0

에서 map 값이 1이니까 탐색을 할 건데.

이미 탐색했음에도 또 탐색하죠. 일단 멤 초과가 안 나도 시간 초과가 나는 건 이상하지 않은 거 같아요.

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

문제

문제

출처

ICPC

메모리 초과를 어떻게 하면 해결 할 수 있을까요?

rhdtka21 5년 전 0

rhdtka21 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말