글 읽기 - 메모리가 왜이렇게 많이 나온건지 잘 모르겠습니다.

swjwpower 3년 전 0

배열쓰면 메모리 터질게 보여서 연결리스트를 이용한 queue를 통해 bfs와 위상정렬로 풀었습니다.

모든 메모리는 해제해 주었고 pop할때마다 지워줫는데 왜이리 많이나왓는지 궁금합니다.

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>
int N, K, startLen = 0;

typedef struct Node {
	int data;
	int enter;
	int parents;
	int time;
	int maxtime;
	struct Node* next;
}Node;

typedef struct queue {
	Node* node;
	struct queue* next;
}queue;

void addChild(Node* node, int data, int time) {
	Node* tmp = malloc(sizeof(Node));
	tmp->data = data;
	tmp->time = time;
	tmp->maxtime = time;
	tmp->next = NULL;
	tmp->parents = 1;
	if ((node)->next == NULL) (node)->next = tmp;
	else {
		tmp->next = (node)->next;
		(node)->next = tmp;
	}
}

void push(Node* node, queue** tail, queue** q) {
	queue* tmp = malloc(sizeof(queue));
	tmp->next = NULL;
	tmp->node = node;

	if (*tail == NULL) {
		*tail = tmp;
		(*q)->next = *tail;
	}
	else {
		(*tail)->next = tmp;
		*tail = tmp;
	}
}

Node* makeNode(Node* node) {
	Node* tmp = malloc(sizeof(Node));
	tmp->data = node->data;
	tmp->enter = node->enter;
	tmp->next = node->next;
	tmp->time = node->time;
	tmp->maxtime = node->maxtime;
	return tmp;
}

int bfs(int start[], Node node[], int win) {
	int i, j, data, enter, data1;
	Node* nodeq = NULL;
	queue* q = malloc(sizeof(Node));
	queue* tail = NULL;
	queue* del;
	for (i = 0; i < startLen; i++) {
		push(makeNode(&node[start[i]]), &tail, &q);
	}

	while (q->next != NULL) {

		nodeq = q->next->node;
		data1 = nodeq->data;
		if (nodeq->data == win) break;
		del = q;
		q = q->next;
		free(del);

		while (nodeq->next != NULL) {
			data = nodeq->next->data;
			if (node[data].enter <= 1) {
				push(makeNode(&node[data]), &tail, &q);
			}
			node[data].enter--;
			if (node[data].maxtime < node[data1].maxtime + node[data].time && node[data].parents>1) node[data].maxtime = node[data1].maxtime + node[data].time;
			else if (node[data].parents <= 1) node[data].maxtime += node[data1].maxtime;
			nodeq = nodeq->next;
		}
	}
	printf("%d\n", node[win].maxtime);
}

int main() {
	int T, x, y, i, win, *start, max;
	Node* building;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &N, &K);
		building = (Node*)malloc(sizeof(Node) * (N + 1));
		for (i = 1; i <= N; i++) {
			scanf("%d", &building[i].time);
			building[i].data = i;
			building[i].parents = 0;
			building[i].enter = 0;
			building[i].maxtime = building[i].time;
			building[i].next = NULL;
		}
		for (i = 0; i < K; i++) {
			scanf("%d %d", &x, &y);
			addChild(&building[x], y, building[y].time);
			building[y].parents++;
			building[y].enter++;
		}
		scanf("%d", &win);
		start = (int*)malloc(sizeof(int) * (N + 1));
		for (i = 1; i <= N; i++) {
			if (building[i].parents == 0) {
				start[startLen++] = i;
			}
		}
		bfs(start, building, win);
		free(start);
		startLen = 0;
		free(building);
	}
}

djm03178 3년 전 0

bfs 도중 win을 만났을 때 큐에 남아있는 원소들에 대한 free가 이루어지지 않는 것 같습니다.

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

문제

문제

출처

ICPC

메모리가 왜이렇게 많이 나온건지 잘 모르겠습니다.

swjwpower 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말