글 읽기 - 메모리초과가떠요..

jhsong206 7년 전 0

지도를 나타낸 2차원 문자 배열이랑 방문 기록 표시할 bool 2차원 배열 썼습니다.

메모리초과 뜨길래 동적할당으로 바꿨는데도 안되네요..

아무리 배열 두 개 썼다지만 128MB는 한참 남아돌것같은데, 다른 곳에 문제가 있는 걸까요

혹시 deque를 이용한 큐를 3개 만들었는데 이게 메모리를 많이 차지하나요??

고수님들 도와주세요

#include<iostream>
#include<algorithm>
#include<deque>

using namespace std;

deque<int> X;
deque<int> Y;
deque<int> cnt;
int N, M;
char **map;
int Max;
int Xdir[4] = { 1, 0, -1, 0 };
int Ydir[4] = { 0, 1, 0, -1 };
bool **boolMap;

void bfs(int x, int y) {
	int num;

	X.push_back(x);
	Y.push_back(y);
	cnt.push_back(0);
	boolMap[y][x] = true;

	while (X.size()) {
		x = X.front();
		X.pop_front();
		y = Y.front();
		Y.pop_front();
		num = cnt.front();
		cnt.pop_front();
		boolMap[y][x] = true;

		for (int i = 0; i < 4; i++) {
			if (x + Xdir[i] >= 0 && x + Xdir[i] < M && y + Ydir[i] >= 0 && y + Ydir[i] < N) {
				if (map[y + Ydir[i]][x + Xdir[i]] == 'L' && boolMap[y + Ydir[i]][x + Xdir[i]] == false) {
					X.push_back(x + Xdir[i]);
					Y.push_back(y + Ydir[i]);
					cnt.push_back(num + 1);
				}
			}
		}
	}
	if (Max < num)
		Max = num;
}

int main() {
	int i, j;
	cin >> N >> M;

	map = new char* [N + 1];
	boolMap = new bool* [N + 1];
	for (i = 0; i < N; i++) {
		map[i] = new char[M + 1];
		boolMap[i] = new bool[M + 1];
	}

	for (i = 0; i < N; i++) 
		cin >> map[i];
	
	for (int k = 0; k < N; k++)
		fill(boolMap[k], boolMap[k] + M, false);

	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (map[i][j] == 'L') {
				bfs(j, i);
				for (int k = 0; k < N; k++)
					fill(boolMap[k], boolMap[k] + M, false);
			}
		}
	}
	printf("%d\n", Max);

	return 0;
}

tols91 7년 전 2

bfs함수에서 push할때 방문체크를 해줘야 할거같아요

jhsong206 7년 전 0

push할때는 아직 방문하지 않은 상태라고 하고 pop하는 시점이 방문한다고 생각해서 그 때 방문체크를 한건데.. 아닌가요?

tols91 7년 전 3

그렇게 되면 큐에 같은 좌표값이 계속 들어갈수도 있어서 메모리초과가 날거에요

큐에 넣으면서 방문체크해줘야 같은 값이 안들어가고 잘나옵니다.

push할때 방문체크해주니 AC받네요

jhsong206 7년 전 0

와 그러네요 감사합니다ㅠㅠ 다시 생각해보니 푸쉬할때 넣어줘야 스택에 중복으로 저장안되서 메모리를 절약할수 있겠네요. 정말 감사합니다

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

문제

문제

출처

ICPC

메모리초과가떠요..

jhsong206 7년 전 0

tols91 7년 전 2

jhsong206 7년 전 0

tols91 7년 전 3

jhsong206 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말