글 읽기 - 1012 C (C++) 메모리초과 도움받고 싶습니다.

acasus 1년 전 0

BFS를 사용해 풀었습니다.

최대 53*53 크기의 int 배열이 항상 준비되어 있는 상태로

queue < pair<int,int> > 에 BFS 과정마다 값을 집어넣는 작업을 하고 있습니다.

아마?도 저 queue의 메모리 최대값은 q.pop이 최소한으로 일어나면서 최대 크기에서 시행되는 경우인, 50*50 크기의 모든 곳에 배추가 존재하는 경우로, queue 안에는 최대 약 2500개 가량의 pair<int,int>가 존재할 것으로 예상됩니다.

어떻게 하면 메모리 사용량을 줄일 수 있을까요?

코드의 내용은 주석으로 간단하게 설명하였습니다.

#include <stdio.h>
#include <queue>
#include <iostream>

using namespace std;
int arr[53][53]; //배추 존재 여부를 1, 0으로 표시.
queue<pair<int, int> > q; //bfs를 위한 queue. 아마도? 최대 약 2500개까지 들어갈 수 있음.


void arrset(void) //arr를 0,0,0,... 으로 초기화.
{
	for(int i=0; i<53; i++)
	{
		for(int j=0; j<53; j++)
		{
			arr[i][j]=0;
		}
	}
}

void printarr(int a, int b) //디버깅용 함수.
{
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<b; j++)
		{
			printf("%d",arr[i][j]);
		}
		printf("\n");
	}
}

void bfs(void) //bfs 함수.
{
	//printf("%d",q.front().second);
	int x, y;
	x=q.front().first;
	y=q.front().second;
	arr[x][y]=2;
	if(arr[x-1][y]==1)
	{
		q.push(make_pair(x-1, y));
	}
	if(arr[x][y+1]==1)
	{
		q.push(make_pair(x, y+1));
	}
	if(arr[x][y-1]==1)
	{
		q.push(make_pair(x, y-1));
	}
	if(arr[x+1][y]==1)
	{
		q.push(make_pair(x+1, y));
	}
}

int main(void)
{
	int T;
	scanf("%d",&T);
	int M, N, K;
	int a1, a2;
	int count=0;
	for(int i=0; i<T; i++)
	{
		scanf("%d %d %d",&M, &N, &K);
		arrset();
		count=0;
		//qclear();
		for(int j=0; j<K; j++) //초기 arr 입력.
		{
			scanf("%d %d",&a1,&a2);
			arr[a1+1][a2+1]=1; //bfs함수의 매끄러운 작동을 위해, arr의 구석은 전부 0으로.
		}
		//printarr(M+2, N+2);
		//printf("%d\n");
		for(int a=0; a<M+2; a++)
		{
			for(int b=0; b<N+2; b++)
			{
				if(arr[a][b]==1)
				{
					//printf("%d %d\n",a,b);
					q.push(make_pair(a, b));
					while(q.size()!=0)
					{
						bfs();
						q.pop(); //bfs함수에서 q에 들어가는 요소는 최대 4개.
                        //4개 들어가면 1개 pop하는, 비효율적인 메모리 할당.
					}
					count=count+1;
				}
			}
		}
		printf("%d\n",count);
	}
}

acasus 1년 전 0

해결했습니다 ㅎㅎ..

질문한게 부끄러울 정도로 간단한 문제였네요

https://www.acmicpc.net/board/...

다음 글의 도움을 받았습니다

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

문제

문제

출처

ICPC

1012 C (C++) 메모리초과 도움받고 싶습니다.

acasus 1년 전 0

acasus 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말