글 읽기 - 왜 메모리 초과가 날까요?

sungdd2 4년 전 0

우선 인접 행렬로 구해봤는데, 벡터를 사용했습니다.

근데 자꾸 메모리 초과가 나오더라구요

이 후에 그냥 동적배열 할당해서 푼 것은 맞았다고 나오는데, 벡터로 구했을 경우에 메모리 초과가 나오는게 의문입니다.

사이즈를 설정해 주었는데도 메모리 초과가 나나요?

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, v;
queue<int> q;
int m_dfs(int number, vector<vector<int>> line, vector<bool>& check_v);
int m_bfs(int number, vector<vector<int>> line, vector<bool>& check_v);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m >> v;

	//인접행렬로 구현.
	
	vector<vector<int>> line(n,vector<int>(n,0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			line[i][j] = 0;
		}
	}

	vector<bool> check_v1(n);
	vector<bool> check_v2(n);

	for (int i = 0; i < n; i++) {
		check_v1[i] = false;
		check_v2[i] = false;
	}
	

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		line[a - 1][b - 1] = 1;
		line[b - 1][a - 1] = 1;
	}
	
	m_dfs(v-1, line, check_v1);
	cout << '\n';
	cout << v << " ";
	check_v2[v - 1] = true;
	q.push(v - 1);

	while(!q.empty()) {
		int x = q.front();
		q.pop();
		m_bfs(x, line, check_v2);
	}
	cout << '\n';

	
	//인접리스트로 구현

	

	return 0;
}

int m_dfs(int number, vector<vector<int>> line, vector<bool>& check_v) {


	check_v[number] = true;

	cout << number + 1 << " ";

	for (int i = 0; i < n; i++) {
		if (!check_v[i] && line[number][i] == 1) {
			m_dfs(i, line, check_v);
		}
	}

	return 0;
}

int m_bfs(int number, vector<vector<int>> line, vector<bool>& check_v) {
	queue<int> q;

	for (int i = 0; i < n; i++) {
		if (!check_v[i] && line[number][i] == 1) {
			q.push(i);
			check_v[i] = true;
			cout << i + 1 << " ";
		}
	}

	return 0;
}

djm03178 4년 전 0

dfs를 할 때 인접 행렬을 값으로 넘겨주고 있기 때문에 재귀가 들어갈 때마다 인접 행렬 전체가 복사되어 스택에 쌓이게 됩니다.

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

문제

문제

출처

ICPC

왜 메모리 초과가 날까요?

sungdd2 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말