글 읽기 - 7576 토마토 메모리초과

neity16 4년 전 0

동작실행은 이상이 없어보이는데 메모리초과가 계속뜨네요.. 메모리초과시 어떻게 해결해야할까요 ㅠㅠ

도움주시면 감사하겠습니다!

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

int dir[4][2] = { {1,0} ,{0,1},{-1,0},{0,-1} };
int board[1000][1000];
int M, N, Q_cnt = 0;
int d_cnt = 0, c_cnt = 0;
queue<pair<int, int>>* p;
int* cnt_p;
bool finish()
{
	for (int i=0;i<N;i++)
	{
		for (int j=0;j<M;j++)
		{
			if (board[i][j] == 0)
				return false;
		}
	}
	return true;
}
bool disable()
{
	for (int i=0;i<Q_cnt;i++)
	{
		if (!p[i].empty())
			return false;
	}
	return true;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	queue<pair<int, int>> ping;
	cin >> M >> N; // M=가로=x , N=세로=y
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
				ping.push({ i,j });
		}
	if (finish())
	{
		cout << 0;
		return 0;
	}
	Q_cnt = ping.size();
	p = new queue<pair<int, int>>[Q_cnt];
	cnt_p = new int[Q_cnt];
	
	for (int i=0;i<Q_cnt;i++)
	{
		auto cur = ping.front();
		ping.pop();
		p[i].push({ cur.first,cur.second });

		cnt_p[i] = 1;
	}
	while (!finish())
	{
		if (disable())
		{
			cout << -1;
			return 0;
		}
		d_cnt++;
			for (int j = 0; j < Q_cnt; j++)
			{
				c_cnt = 0;
				int q = cnt_p[j];
				while (q--)
				{
					auto cur = p[j].front();
					p[j].pop();
					for (int k = 0; k < 4; k++)
					{
						int n_y = cur.first + dir[k][0];
						int n_x = cur.second + dir[k][1];
						if ((n_x >= M) || (n_y >= N) || (n_x < 0) || (n_y < 0))
							continue;
						if ((board[n_y][n_x] == -1) || (board[n_y][n_x]))
							continue;
						board[n_y][n_x] = 1;
						p[j].push({ n_y,n_x });
						c_cnt++;
					}
				}
				cnt_p[j] = c_cnt;
			}
	}
	delete [] cnt_p;
	delete [] p;
	cout << d_cnt;
	return 0;
}

bupjae 4년 전 1

이 프로그램은 최악의 경우 999,999 개의 queue<pair<int, int>> 객체를 만들게 됩니다. 비어있는 queue<pair<int, int>> 의 정확한 크기는 구현체마다 다르겠지만, 주어진 메모리 제한을 지키기는 쉽지 않을 겁니다.

동적 배열 p로 하려고 했던 것을 더 효율적인 방법으로 하셔야 합니다.

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

문제

문제

출처

ICPC

7576 토마토 메모리초과

neity16 4년 전 0

bupjae 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말