글 읽기 - 이 코드가 구조적으로 문제가 있나요?

soloranker66 4년 전 0

이 코드가 구조적으로 문제가 있는건가요..?

계속 이 부위 저 부위 빼봐도 128MB를 넘어가서 메모리초과가 뜹니다..

문제의 정답여부를 떠나 메모리 초과가 뜨는 이유를 알고싶습니다.

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

typedef struct Queue {
	int data;
	struct Queue *next;
}Queue;
typedef struct _node {
	int link, size, Indegree;
	int *linked;
}_node;

int QueueCount = 0;
Queue *Front, *Rear;
void Push(int data, int Depth), Pop(), vectorFull(int temp);
_node *arr;

int main() {
	int size, edge;
	scanf("%d %d", &size, &edge);
	arr = malloc(sizeof(_node)*(size+1));
	for (int i = 1; i <= size; i++) {
		arr[i].link = 0;
		arr[i].size = 5;
		arr[i].Indegree = 0;
		//arr[i].Depth = 0;
		arr[i].linked = malloc(sizeof(int) * 2);
	}
	while (edge--) {
		int temp1, temp2;
		scanf("%d %d", &temp1, &temp2);
		arr[temp1].linked[arr[temp1].link++] = temp2;
		arr[temp2].Indegree++;
		if (arr[temp1].link == arr[temp1].size)
			vectorFull(temp1);
	}
	for (int i = 1; i <= size; i++)
		if (arr[i].Indegree == 0)
			Push(i, 0);
	while (QueueCount) {
		int pos = Front->data;
		Pop();
		printf("%d ", pos);
		for (int i = 0; i < arr[pos].link; i++) {
			arr[arr[pos].linked[i]].Indegree--;
			if (arr[arr[pos].linked[i]].Indegree == 0)
				Push(arr[pos].linked[i], 1);
		}
	}
}
void Push(int data, int Depth) {
	Queue *node = malloc(sizeof(Queue));
	node->data = data;
	//arr[data].Depth = Depth;
	if (QueueCount >= 1) {
		Rear->next = node;
	}
	else {
		Front = node;
		Rear = node;
	}
	QueueCount++;
}
void Pop() {
	QueueCount--;
	Queue *Del = Front;
	Front = Front->next;
	free(Del);
}
void vectorFull(int temp) {
	arr[temp].linked = realloc(arr[temp].linked, (arr[temp].size *2) * sizeof(int));
	arr[temp].size *= 2;
}

chogahui05 4년 전 0

메모리 초과는 잘 모르겠어요.

그런데, 그것 외에 문제가 될 소지는 굉장히 많아 보입니다.

1. realloc 사용법이 저게 맞나요..? realloc의 특성상, 메모리 할당에 실패하면 NULL을 리턴할 건데. 그 경우에 복구는 어떻게 시키나요?

2. 아마 노드 안에 배열이 있는 걸로 봐서는 동적 배열 비스무리하게 구현하셨네요.

그런데 linked에 할당된 건 2인데, 초기 size (capacity)는 5네요. 둘은 맞춰주셔야 하지 않을까요?

soloranker66 4년 전 0

문제 푸는데 메모리제한은 128MB이기에 realloc 할당에 문제가 생길게 없을거라고 예상했구

link는 현재 연결된수, size는 현재 연결할 수 있는 최대치라

size 최대치에 도달했을때 realloc으로 배열을 늘려 추가할당할 수 있게 만들어놧어요

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

문제

문제

출처

ICPC

이 코드가 구조적으로 문제가 있나요?

soloranker66 4년 전 0

chogahui05 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말