글 읽기 - 1012번 유기농 배추 문제에서 메모리 초과 원인을 모르겠습니다.

ace012 9년 전 0

밭 크기나 큐 크기도 딱히 문제될 게 없는데 메모리 초과가 뜨네요

메모리 초과가 뜰 만한 부분이 대체 어디인지 모르겠습니다

찾아주세요 ㅠㅠ

#include<cstdio>
#include<queue>
using namespace std;

int map[52][52],t,m,n,c,tmp_x,tmp_y,d[4][2]={{1,0},{0,1},{-1,0},{0,-1}},s;
queue< pair<int,int> > q;

void BFS(int x,int y){
	map[x][y]=0;
	q.pop();
	for(int i=0;i<4;i++){
		if(map[x+d[i][0]][y+d[i][1]]==1){
			q.push(make_pair(x+d[i][0],y+d[i][1]));
		}
	}
}

int main(){
	scanf("%d",&t);
	while(t--){
		s=0;
		scanf("%d%d%d",&m,&n,&c);
		for(int i=0;i<n+2;i++)
			for(int j=0;j<m+2;j++)
				map[i][j]=0;
		for(int i=0;i<c;i++){
			scanf("%d%d",&tmp_x,&tmp_y);
			map[tmp_y+1][tmp_x+1]=1;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(map[i][j]==1){
					s++;
					q.push(make_pair(i,j));
					while(q.size()){
						BFS(q.front().first,q.front().second);
					}
				}
			}
		}
		printf("%d\n",s);
	}
	return 0;
}

hihihi 9년 전 0

큐에 엄청마니들어가나봐여

wwiiiii 9년 전 0

문제점을 찾았으면 댓글로 올려주세요!

ace012 9년 전 0

아마도 맵 초기화 문제로 에러가 발생한 것 같습니다

큐에서 뺄 때 지난 맵을 0으로 초기화해주니까 되네요

근데 틀린 이유가 메모리 초과인 이유는 모르겠네요

wwiiiii 9년 전 0

아마도 지난 맵이 계속 1로 되어있어서 큐에 계속 들어가는걸로 추정되는데요 ㄷㄷ

Nada 9년 전 0

원인은 깊이가 같을 때 방문하지 않아야 하는데 위 소스는 방문하고 정답소스는 방문하지 않네요.

예를들어

2 3

3 4 5

깊이로 나눠봤을 때

2번에서 (3번과 4번을 갈 수 있어 큐에 넣고)

3번에서 (4번과 5번에서 갈 수 있어 큐에 넣는데)

4번을 두 번 방문하게 됩니다.

단 수정된 부분은 넣기 전에 map을 변경하셔서 3번에서 4번을 방문하지 않고 넘어가게 됩니다.

이게 누적되면서 메모리가 초과 될 정도로 계산량이 늘어나게 되는거죠.

dhcshc 6년 전 0

12 ~ 13 라인 사이에

map[x+d[i][0]][y+d[i][1]] = 0;

추가하면 AC가 나옵니다.

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

문제

문제

출처

ICPC

1012번 유기농 배추 문제에서 메모리 초과 원인을 모르겠습니다.

ace012 9년 전 0

hihihi 9년 전 0

wwiiiii 9년 전 0

ace012 9년 전 0

wwiiiii 9년 전 0

Nada 9년 전 0

dhcshc 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말