글 읽기 - C 메모리 초과가 떠요

kanghun8871 5년 전 0

코드는 별 문제 없는 거 같은데

메모리 초과가 뜨네요ㅠ

좀 더 효율적으로 짤 수 있는 방법이 있을까요?

지름 구할 때 한 점에서 가장 먼 점 구하고 그 점에서 가장 먼 점의 거리가 지름인 건 알겠는데

제가 짠 코드의 형식으로 어떻게 구현할지는 모르겠어요ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int N;
int** graph;
int* out;
int* dist;
int max = 0;

int dfs(int num) {
	out[num] = 1;
	int i;
	int distance;
	int max=0;
	int flag = 0;
	for (i = 1;i <= N;i++) {
		if ((graph[num][i] != 0) && (out[i] == 0)) {
			flag = 1;
			distance = graph[num][i] + dfs(i);
			if (distance > max) { max = distance;}
		}
	}
	if (flag==0)return 0;
	return max;
}
int main(){
	int i, j;
	int a, b;
	scanf("%d", &N);


	graph = (int**)malloc(sizeof(int)*(N + 1));
	out = (int*)malloc(sizeof(int) + (N + 1));
	dist = (int*)malloc(sizeof(int) + (N + 1));

	for (i = 0;i <= N;i++) {
		graph[i] = (int*)malloc(sizeof(int) * (N + 1));
		out[i] = 0;
	}
	for (i = 0;i <= N;i++) {
		for (j = 0;j <=N;j++) {
			graph[i][j] = 0;
		}
	}
	for (i = 1;i <= N;i++) {
		scanf("%d", &i);
		while (1) {
			scanf("%d", &a);
			if (a == -1)break;
			scanf("%d", &b);
			graph[i][a] = b;
		}
	}

	for (i = 1;i <= N;i++) {
		dist[i] = dfs(i);
		if (dist[i] > max)max = dist[i];
	}

	printf("%d", max);

	return 0;
}

djm03178 5년 전 1

지금 코드와 같이 graph[a][b]로 간선을 표현하는 것을 인접 행렬이라고 합니다.

하지만 이는 N^2개의 간선에 대한 유무를 모두 표현하기 때문에 트리에서는 매우 비효율적입니다. 트리에는 간선이 N-1개밖에 없습니다.

이를 위해서 사용할 수 있는 것이 인접 리스트입니다. 인접 리스트는 한 정점에 연결된 존재하는 간선들만 모으기 때문에 낭비가 없습니다. C에서는 링크드 리스트 등으로 표현이 가능합니다.

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

문제

문제

출처

ICPC

C 메모리 초과가 떠요

kanghun8871 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말