글 읽기 - 트리의 지름 인접행렬 만들어서 풀면 무조건 메모리 초과가 나나요?

tjqansthd 5년 전 0

저는 트리의지름을

인접행렬을 구한 후

자식의 노드가 하나인 노드부터 자식의 노드가 하나인 노드까지 거리들을

재귀함수를 이용하여

다 구해서 최대값을 내는 방식으로 하였는데

메모리 초과가 나더라고요

인접행렬에 두 노드사이의 weight값도 필요하다 생각해서

웨이트와 상태 두개를 담는 구조체 배열로 인접행렬을 선언했는데

이거때문에 메모리초과가 나는걸까요..?

혹시 몰라서 두 변수를 short로 선언했는데도 메모리초과는 계속 나네요 ㅠ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node {
	short weight;
	short state;
}node;
int max = 0, idx = 1, flag = 0;
void find_next_node(int index, int own, int other, int height, node **tree, int size);
int main() {
	int n, parent, son, weight_tmp, cnt = 0, sum = 0,height=0,tmp=0,tmp2=0;
	int i,j;
	scanf("%d", &n);
	node **tree1 = (node **)calloc(n+1, sizeof(node *));
	int *list = (int *)calloc(n + 1, sizeof(int));
	for (i = 0; i < n + 1; i++) {
		*(tree1 +i) = (node *)calloc(n + 1, sizeof(node));
	}
	for (i = 1; i < n; i++) {
		scanf("%d %d %d", &parent, &son, &weight_tmp);
		tree1[parent][son].state = 1;
		tree1[son][parent].state = 1;
		tree1[parent][son].weight = weight_tmp;
		tree1[son][parent].weight = weight_tmp;
	}
	for (i = 1; i < n + 1; i++) {
		for (j = 1; j < n + 1; j++) {
			if (tree1[i][j].state == 1)sum++;
		}
		if (sum == 1) {
			list[cnt++ + 1] = i;
		}
		sum = 0;
	}

	j = 1;
	for (i = 1; i < cnt+1; i++) {
		while (1) {
			if (tree1[list[i]][j].state == 1) {
				height += tree1[list[i]][j].weight;
				tmp = list[i];
				tmp2 = j;
				j = 1;
				break;
			}
			j++;
		}
		find_next_node(j, tmp2, tmp, height, tree1, n);
		height = 0;
	}
	printf("%d\n", max);
	for (i = 0; i < n + 1; i++)free(*(tree1 + i));
	free(tree1);
	free(list);
	return 0;
}
void find_next_node(int index, int own, int other, int height, node **tree, int size) {
	while (1) {
		if (index == other) {
			index++;
			continue;
		}
		if (tree[own][index].state == 1) {
			height += tree[own][index].weight;
			
			find_next_node(idx, index, own, height, tree, size);
			if (max <= height) {
				max = height;
			}
			height -= tree[own][index].weight;
		}
		(index)++;
		if (index > size) {
			return;
		}
	}
}

djm03178 5년 전 0

한 번 메모리 양을 직접 계산해보시는 게 어떨까요?

n은 당연히 최대인 10000을 가정하고, short가 2바이트라는 점, node가 short 2개로 이루어져있다는 점을 생각해서 계산해보세요.

tjqansthd 5년 전 0

weight는 연결된 노드끼리만 존재한다는걸 토대로

state 변수를 지우고 weight 하나만 남기니까 100mb가 맞춰져서 간신히 풀었네요 ㅎㅎ 감사합니다

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

문제

문제

출처

ICPC

트리의 지름 인접행렬 만들어서 풀면 무조건 메모리 초과가 나나요?

tjqansthd 5년 전 0

djm03178 5년 전 0

tjqansthd 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말