글 읽기 - 1325 c++ 메모리초과 도와주세요 ㅠㅠ

chaeaok 4년 전 0

자꾸 메모리초과가 나네요.. 어디가 문젤까요??

#include <iostream>
#include <vector>
using namespace std;
#define MAX_SIZE 10001

int N, M;
int arr[MAX_SIZE][MAX_SIZE];
int INF = 101;

void floyd() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (k == i || i == j || j == k) continue;
				if (arr[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j];
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	vector<int> v(N + 1);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			arr[i][j] = INF;
		}
	}
	while (M--) {
		int x, y; cin >> x >> y;
		arr[y][x] = 1;
	}
	floyd();
	int max = 0;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] < INF) cnt++;
		}
		v[i] = cnt;
		if (max < v[i]) max = v[i];
	}
	for (int i = 1; i <= N; i++) {
		if (max == v[i]) cout << i << ' ';
	}
}

djm03178 4년 전 1

7번째 줄 그 자체가 문제입니다.

chaeaok 4년 전 0

인접행렬로 풀면 메모리초과가 난다는 말씀이죠????

인접 리스트로 풀어야하나요?

djm03178 4년 전 1

간선의 수의 최댓값이 10만이기 때문에 정점의 수의 제곱의 최댓값에 한참 못 미칩니다. 이런 경우는 인접 행렬보다 인접 리스트가 훨씬 효율적입니다.

사실 인접 행렬로도 int 대신 더 작은 자료형이나 아예 비트 단위로만 체크하면 메모리 초과는 피할 수 있지만, 시간 복잡도가 문제가 됩니다.

chaeaok 4년 전 0

네 풀었어요!

인접리스트로 풀려니까 플로이드는 못쓰겠어서 dfs로 풀었네요 감사합니다.

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

문제

문제

출처

ICPC

1325 c++ 메모리초과 도와주세요 ㅠㅠ

chaeaok 4년 전 0

djm03178 4년 전 1

chaeaok 4년 전 0

djm03178 4년 전 1

chaeaok 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말