글 읽기 - 백준 서버의 스택 메모리 깊이?

hy2850 3년 전 0

안녕하세요.

1743번 문제를 재귀를 사용한 DFS로 풀어봤는데, 백준에선 맞았다고 나오지만, 로컬 환경 (Visual Studio C++ 2019) 에선 프로그램이 돌다가 죽어버립니다.

쓰레기 n개가 (1,1) 부터 한 행마다 쭉 나란히 이어지도록 만들어서, 답은 n이 나와야 합니다.

100 100 n

1 1

1 2

1 3

...

1 100

2 1

...

이런식입니다.

대략 n=4000 까지는 답이 잘 나오다가, 5000 정도부터는 스택오버플로우 에러가 뜨면서 프로그램이 죽어버립니다.

함수가 호출될떄는 메모리 스택영역에 정보를 저장한다고 알고 있는데, 백준 서버의 스택 메모리 영역은 10000번의 함수 호출을 담을 만큼 충분한건가요?

또, 문제에서 주어지는 128 MB 메모리 제한이, 이 함수호출스택 영역과도 관련 있는 제한인지 궁금합니다.

즉 재귀함수를 짤 때, 주어진 메모리 제한을 신경쓰면서 호출 횟수를 제한시키는게 맞는지요?

#include <bits/stdc++.h>	
using namespace std;

typedef pair<int, int> pii;
vector<pii> direction = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; // E S W N
int world[101][101], N, M, cnt = 0;

void DFS(int x, int y) {
	cnt++;

	for (int i = 0; i < 4; i++) {
		int x_next = x + direction[i].first;
		int y_next = y + direction[i].second;

		// Boundary check & Skip if not trash
		if (!(1 <= x_next && x_next <= N && 1 <= y_next && y_next <= M) || world[x_next][y_next] != 1)
			continue;

		// trash detected
		world[x_next][y_next] = -1; // 방문처리
		DFS(x_next, y_next);
	}
}

int main()
{
#ifdef DBG
	random_world_generator(100, 100, 10000); // Test case 생성 (N, M, K = 100, 100, 10000)
	freopen("input.txt", "r", stdin);
#endif
    
	memset(world, 0, sizeof(world));
	int trash_num;
	scanf("%d%d%d", &N, &M, &trash_num);
	for (int i = 0; i < trash_num; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		world[x][y] = 1;
	}

	int max_bunch = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (world[i][j] == 1 && world[i][j] != -1) { // skip explored trash
				world[i][j] = -1;
				cnt = 0;
				DFS(i, j); // 첫번째 DFS 콜에서 안넘어가고 스택오버플로우; n>5000
				max_bunch = max(max_bunch, cnt);
			}
		}
	}

	printf("%d", max_bunch);
}

hy2850 3년 전 1

찾아보니까, 백준 사이트의 경우 스택 메모리 제한이 없다고 합니다.

제 로컬 환경에선 스택 메모리 제한때문에 런타임 에러가 나는 것 같네요.

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