글 읽기 - 메모리 초과가 나네요 (c++)

okemosboy 4년 전 0

벡터 배열을 사용하면 통과하긴하는데 이중벡터를 사용하면 오류가 나네요 그 이유가 궁금합니다.

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
using namespace std;
void dfs(int start, bool visited[], vector<vector<int>> a) {
	
	visited[start] = true;

	for (int i = 0; i < a[start].size();i++) {
		int y=a[start][i];
		if(!visited[y]){
            dfs(y,visited,a);
        }
	}
}
int main() {
	int n, m;
	int ans=0;
	
	scanf("%d%d", &n, &m);
	vector<vector<int>>a(1001);
	bool visited[1001];
	while (m--) {
		int x, y;
		scanf("%d%d",&x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
		
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			dfs(i,visited,a);
			ans++;
		}
	}
	printf("%d", ans);
	
}

djm03178 4년 전 0

코드가 깨지지 않게 다시 올려주세요.

okemosboy 4년 전 0

다시 올렸습니다.

djm03178 4년 전 1

5번째 줄의 vector<vector<int>> a는 벡터의 내용을 모조리 통째로 복사해서 새로운 벡터를 만들어 사용하는 것이기 때문에 재귀 호출을 할 때마다 전체 인접 리스트가 복제되어 쌓이게 됩니다. 재귀 호출이 깊어질수록 더욱 많은 메모리를 차지하고 있게 됩니다.

이런 걸 위해 C++에서는 참조자라는 편리한 문법을 제공합니다.

okemosboy 4년 전 0

아 함수를 호출할때마다 벡터를 새로 만들어서 메모리에 쌓이는군요.... 감사합니다.

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

문제

문제

출처

ICPC

메모리 초과가 나네요 (c++)

okemosboy 4년 전 0

djm03178 4년 전 0

okemosboy 4년 전 0

djm03178 4년 전 1

okemosboy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말