글 읽기 - 메모리초과가 왜 뜰까요...도와주세요

cgin 4년 전 0

-bfs를 통해 시작점에서 각 노드들까지의 최단거리를 vector의 v pair를 이용하여 저장

-탐색이 끝나면 v를 거리에 따라서 sort 같으면 가장 노드의 숫자가 작은것으로 앞으로 하였음

-메모리 초과 발생

-변수 v에는 아무리 많이 할당되도 n보다 작음

-변수 q에 많이 저장해서 초과발생? 인것인지 알 수가 없음

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
int graph[20001][20001];
bool visit[20001];

vector<pair<int, int>> v;

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second > b.second) {
		return true;
	}
	else if (a.second == b.second) {
		return a.first < b.first;
	}
	else {
		return false;
	}
}
void bfs() {
	queue<int> q;
	q.push(1);
	visit[1] = true;
	int length = 0;
	while (!q.empty()) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			int x = q.front();
			v.push_back({ x,length });
			q.pop();
			for (int k = 1; k <= n; k++) {
				if (graph[x][k] == 1 && visit[k] == false) {
					q.push(k);
					visit[k] = true;
				}
			}
		}
		length++;
	}
}
int main() {

	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		graph[x][y] = 1;
		graph[y][x] = 1;
	}

	bfs();

	int size = v.size();
	sort(v.begin(), v.end(), compare);

	int maxsize = v[0].second;
	int count = 0;
	for (int i = 0; i < size; i++) {
		if (v[i].second == maxsize) {
			count++;
		}
	}

	cout << v[0].first << " " << maxsize << " " << count << "\n";

	return 0;
}

djm03178 4년 전 2

graph 자체가 메모리 초과입니다.

int형 약 4억 개면 1.6GB 정도 됩니다.

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

문제

문제

출처

ICPC

메모리초과가 왜 뜰까요...도와주세요

cgin 4년 전 0

djm03178 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말