글 읽기 - 메모리 초과 질문입니다.

skyinyour 6년 전 0

처음에는 큐를 사용해서 메모리초과가 나서 큐가 원인이라 생각했습니다.

다시 생각해보니 비슷할 것 같은데 struct 배열을 사용하여 다시 풀어보았지만

메모리 초과가 어디서 어떻게 왜 나는지 모르겠네요 ㅠㅠ

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

int map[5001][5001];
int visited[5001][5001];
int R[5001];


int px[4] = { 1, 0, -1, 0 }; // down right up left
int py[4] = { 0, 1, 0, -1 };


bool flag = false;
struct pos{
	int x;
	int y;
};
pos arr[5001];
queue<pos> Q;
int cnt;
int index = 0;
int N;
void F(int xt, int yt, int R){
	
	for (int i = xt - R; i <= xt + R; i++){
		for (int j = yt - R; j <= yt + R; j++){
			if (i < 0 || j < 0 || i >= 5001 || j >= 5001 || (i==xt && j==yt)) continue;

			if (map[i][j] != 1) map[i][j] = 1;		
		}
	}

	

}

void dfs(int x, int y){

	if (index >= N) return;

	if (x == arr[index].x && y == arr[index].y){
		cnt--;   // (x,y) ~ (x1,y1) 까지 경로가 존재하면 두 그룹을 하나로 합칠 수 있기에 그룹의 수를 1 차감시켜 줍니다.
		flag = true;
		return;
	}
	
	if (flag) return;

	if (visited[x][y] == 1) return;
	else visited[x][y] = 1;

	for (int i = 0; i < 4; i++){
		int x_ = x + px[i];
		int y_ = y + py[i];
		if (x_ < 0 || x_ >= 5001 || y_ < 0 || y_ >= 5001) continue;

		if (map[x_][y_] == 0) continue;

		if (map[x_][y_] == 1 && visited[x_][y_] == 0){
			dfs(x_, y_);
		}

	}
}
void init(){   // mmset 대신에 직접 초기화 해주었습니다. cstring을 include 하니 index나 이러한 전역변수에서 자꾸 재선언 되었다고 에러가 났습니다.

	for (int i = 0; i < 5001; i++){
		for (int j = 0; j < 5001; j++){
			visited[i][j] = 0;
			map[i][j] = 0;
		}
	}

	for (int i = 0; i < 5001; i++){
		arr[i].x = 0;
		arr[i].y = 0;
	}
}
int main(){

	int T;
	cin >> T;

	while (T--){

		init();
		int x, y;
		cin >> N;
		cnt = N;

		
		for (int i = 0; i <N; i++){
			cin >> x >> y >> R[i];
			arr[i].x = x;
			arr[i].y = y;
			map[x][y] = 1;
		}
		int i = 0;
		int j = 0;
		while (j < N){         // 여기서는 map에 x,y 를 기준으로 R 범위내에 있는 좌표를 모두 1로 만들어줍니다.

			int nx = arr[j].x;
			int ny = arr[j].y;
			F(nx, ny, R[i++]);
			j++;
		}
		j = 0;
		while (j < N){         // map 이 셋팅된 후, (x,y) ~ (x1,y1) 까지 경로가 존재하면 그룹의 갯수를 1씩 차감하도록 하였습니다.
			int nx = arr[j].x;
			int ny = arr[j].y;
			index = ++j;
			dfs(nx, ny);
			flag = false;
		}

	

		cout << cnt << endl;

	}
	
	system("pause");

	return 0;
}

djm03178 6년 전 0

dfs가 무려 2500만 개의 점을 탐색하게 될 텐데, 재귀 호출에 대한 정보는 스택 영역에 할당되므로 8MB 이상을 사용할 수가 없는데 이는 이를 훨씬 초과하게 됩니다.

애초에, 이 문제를 모든 가능한 좌표를 하나씩 방문하면서 푸는 건 무리라고 생각합니다.

skyinyour 6년 전 0

아하.. 다른 방법을 찾아봐야겠네요 ㅠㅠ

근데 여기서 더 여쭤보고싶은게 있습니다!

1. 스택 영역에는 왜 8MB 이상 사용 할 수 없나요?

2. 제가 접근한 방법에서는메모리가 그러면 4 byte * 2500만 정도를 사용하는건가요?

3. 보통 메모리 계산? 추정을 어떤식으로 하나요.. ? ㅠㅠ

djm03178 6년 전 1

1. 저도 정확한 이유는 모르겠지만, 운영체제마다 보통 1MB ~ 8MB를 스택 영역의 기본 한계로 잡습니다. 조정은 가능하다고 알고 있지만, 온라인 저지에서는 어떻게 할 수가 없습니다.

2. 4바이트 정도가 아니라, dfs에 전달되는 인자만 4바이트 2개에 8바이트고, 여기에 리턴 주소와 함수 내부에 선언된 지역변수들 등까지 계산하면 매 호출마다 20바이트는 넘어가리라고 생각됩니다. 재귀함수에서 조심해야 할 부분 중 하나인데, 호출 스택이 메모리에 그대로 쌓여가기 때문에 깊이가 깊어지는만큼 메모리 사용량이 늘어나게 됩니다.

djm03178 6년 전 1

3. 메모리 계산도 시간복잡도 계산하고 비슷합니다. 일단 지역이나 전역변수로 처음부터 크기가 고정되어 있는 것은 그대로 계산하면 되고, 여기에 동적으로 할당되는 메모리 공간들이나 재귀호출 같은 것들은 그 입력에 따라서 얼마나 크기가 할당되고 얼마나 깊이가 들어가는지를 파악하면 됩니다.

예를 들어, int n; scanf("%d", &n); int dp[n][n]; 은 O(N^2)의 메모리를 요구한다는 걸 쉽게 알 수 있습니다.

skyinyour 6년 전 0

아하.. 상세한 답변 너무 감사합니다 ㅠㅠ 더 공부해야할 방향이 잡히네요!! 감사합니다 :)

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

문제

문제

출처

ICPC

메모리 초과 질문입니다.

skyinyour 6년 전 0

djm03178 6년 전 0

skyinyour 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

skyinyour 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말