글 읽기 - 메모리 초과!!!

sotter1020 5년 전 0

메모리 초과 질문입니다.

주석을 써놨기 때문에 코드 이해는 어렵지 않을 거라 생각됩니다.

메모리 초과 문제들 다 못 풀고 있는데

어떤식으로 접근해서 해결해야 되는지 알려주시면 감사하겠습니다.

#include<iostream>
#include<queue>

using namespace std;

int n, m;
int day = -1;
int adj[4][2] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};

int box[1001][1001];
bool visited[1001][1001];

void show() {
	for (int y = 1; y <= m; ++y) {
		for (int x = 1; x <= n; ++x)
			cout << box[y][x] << " ";
		cout << endl;
	}

}

void allRiping(queue<pair<int, int>> pre) {
	if (pre.size() == 0) return;
	queue<pair<int, int>> cur;
	while(!pre.empty()) {				// pre큐에서의 좌표값에서 인접한 좌표중 0이면서 방문하지 않은 좌표를 cur에 담고, 1로 바꾼다.
		int y = pre.front().first;
		int x = pre.front().second;
		for (int k = 0; k < 4; ++k) {
			int new_y = y + adj[k][0];
			int new_x = x + adj[k][1];

			
			
			if (new_x <= 0 || new_x > n) 
				continue;

			if (new_y <= 0 || new_y > m)
				continue;

			if (visited[new_y][new_x])
				continue;

			int& coord = box[new_y][new_x];
			if (coord == 0) {
				coord++;
				cur.push(make_pair(new_y, new_x));
				visited[new_y][new_x] = true;
			}
		}
		pre.pop();
	}
	day++;
	allRiping(cur); // recursion한다.
}

int checkRiping() {
	for (int y = 1; y <= m; ++y)
		for (int x = 1; x <= n; ++x)
			if (box[y][x] == 0)
				return -1;
	return day;
}

int main() {
	cin >> n >> m;
	queue<pair<int, int>> init;   // 초기좌표
	for (int y = 1; y <= m; ++y)
		for (int x = 1; x <= n; ++x) {
			cin >> box[y][x];
			if (box[y][x] == 1) {
				init.push(make_pair(y, x)); // 처음에 1인 좌표들을 queue에 담는다.
				visited[y][x] = true;
			}
		}
	
	allRiping(init);
	cout << checkRiping() << endl;
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과!!!

sotter1020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말