글 읽기 - 살려주십쇼 런타임에러 DoubleFree

jinwhan 2년 전 0

처음에 인접행렬로 풀고 어? 쉽네 했다가 메모리초과...

다음엔 단순 연결 리스트로 풀었다가 시간초과...

결국 우선순위 큐로 풀고 있는데 생전 처음보는 에러가 나는데 어디서나는지 찾지 못해 질문드립니다.

free를 사용하는 함수가 pop, choose, shortest_path인데

choose와 shortest_path는 pop함수내에서 새로 할당한 노드를 free하고있고,

pop함수는 힙에 노드가 없으면 호출 자체를 하지 않도록 구현했고 pop에서 free하는건 힙에 노드가 하나만 있을때 해당노드를 free하는것과

pop_pos에서 리턴받은 노드를 free하는건데

pop_pos에서 while문이 끝나는 경우는 트리의 높이가 1이하인 경우로 가능한 트리는 노드의 수가 1,2,3인 완전이진트리입니다.

1,3 일때 is_full이 true이고 3인경우 rightchild를 리턴, 1은 자기자신을 리턴. 2인경우 leftchild를 리턴하기때문에 free할 노드가 NULL이 아니라 생각합니다

근데 DoubleFree라는 생전 처음보는 에러가 나와서 머리가 정지하네요...

제발 살려주세요...

이 문제 티어가 왜 골드5일까요...

결국 저는 실버인가봅니다...ㅠㅠㅠ

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0

typedef struct treenode* treepointer;
typedef struct treenode {
	int vertex, weight, height;
	short int is_full;
	treepointer parent, leftchild, rightchild;
}treenode;
typedef struct heapnode* heappointer;
typedef struct heapnode {
	int weight;
	short int is_found;
	treepointer top;
}heapnode;

heappointer heap[20005];
int found[20005] = { 0, };

void create_heap(int);
void add_edge(int, int, int);
void update(treepointer);
treepointer push_pos(heappointer);
void push(heappointer, int,int);
treepointer pop_pos(heappointer);
treepointer pop(heappointer);
int choose(int);
void shortest_path(int, int);
//void dfs(treepointer t) {
//	if (!t) return;
//	printf(" %d(%d,%d,%d) ", t->vertex, t->weight, t->height,t->is_full);
//	dfs(t->leftchild);
//	dfs(t->rightchild);
//}
//void print_heap(int vertex) {
//	for (int i = 1; i <= vertex; i++) {
//		printf("src:%d, dst(wgt,hgt,full)\n", i);
//		if(heap[i]->top)printf("top is %d(%d %d %d)\n", heap[i]->top->vertex, heap[i]->top->weight, heap[i]->top->height, heap[i]->top->is_full);
//		dfs(heap[i]->top);
//		printf("\n");
//	}
//}
int main() {
	int vertices, edge, start;
	int u, v, w;
	scanf("%d %d", &vertices, &edge);
	scanf("%d", &start);
	create_heap(vertices);
	while (edge--) {
		scanf("%d %d %d", &u, &v, &w);
		add_edge(u, v, w);
		//print_heap(u);
	}
	//print_heap(vertices);
	shortest_path(start, vertices);

	for (int i = 1; i <= vertices; i++) {
		if (heap[i]->is_found) printf("%d\n", heap[i]->weight);
		else printf("INF\n");
	}
	return 0;
}

void create_heap(int size) {
	for (int i = 1; i <= size; i++) {
		heap[i] = (heappointer)malloc(sizeof(heapnode));
		heap[i]->is_found = FALSE;
		heap[i]->top = NULL;
		heap[i]->weight = 0;
	}
}
void add_edge(int src, int dst, int wgt) {
	//printf("call add_edge\n");
	if (heap[src]->top == NULL) {
		heap[src]->top = (treepointer)malloc(sizeof(treenode));
		heap[src]->top->height = 0;
		heap[src]->top->is_full = TRUE;
		heap[src]->top->leftchild = NULL;
		heap[src]->top->parent = NULL;
		heap[src]->top->rightchild = NULL;
		heap[src]->top->vertex = dst;
		heap[src]->top->weight = wgt;
		return;
	}
	else push(heap[src], dst, wgt);
}
void update(treepointer last) {
	//printf("call update %d(%d,%d,%d)\n",last->vertex,last->weight,last->height,last->is_full);
	while (last) {
		if (!(last->leftchild)) {
			last->is_full = TRUE;
			last->height = 0;
			last = last->parent;
			continue;
		}
		if (!(last->rightchild)) {
			last->is_full = FALSE;
		}
		else if (last->leftchild->height == last->rightchild->height) {
			if (last->rightchild->is_full) last->is_full = TRUE;
			else last->is_full = FALSE;
		}
		else {
			last->is_full = FALSE;
		}
		last->height = last->leftchild->height + 1;

		last = last->parent;
	}
}
treepointer push_pos(heappointer root) {
	//printf("call push_pos\n");
	treepointer last = (treepointer)malloc(sizeof(treenode));
	treepointer temp = root->top;
	last->height = 0;
	last->is_full = TRUE;
	last->leftchild = NULL;
	last->rightchild = NULL;
	while (temp->height>1) {
		if (temp->is_full) temp = temp->leftchild;
		else if (temp->leftchild->is_full) temp = temp->rightchild;
		else temp = temp->leftchild;
	}
	if (temp->is_full) {
		if (temp->height) temp = temp->leftchild;
		temp->leftchild = last;
	}
	else temp->rightchild = last;
	last->parent = temp;
	return last;
}
void push(heappointer root, int dst, int wgt) {
	//printf("call push\n");
	treepointer last = push_pos(root);
	treepointer temp = last;
	while (temp->parent) {
		if (temp->parent->weight > wgt) {
			temp->weight = temp->parent->weight;
			temp->vertex = temp->parent->vertex;
			temp = temp->parent;
		}
		else break;
	}
	temp->weight = wgt;
	temp->vertex = dst;
	update(last->parent);
}
treepointer pop_pos(heappointer root) {
	treepointer temp = root->top;
	while (temp->height>1) {
		if (temp->is_full) temp = temp->leftchild;
		else if (temp->rightchild->is_full == FALSE) temp = temp->rightchild;
		else temp = temp->leftchild;
	}
	if (temp->is_full) {
		if (temp->height) temp = temp->rightchild;
	}
	else temp = temp->leftchild;
	return temp;
}
treepointer pop(heappointer root) {
	//printf("call pop\n");
	treepointer top = (treepointer)malloc(sizeof(treenode));
	top->vertex = root->top->vertex;
	top->weight = root->top->weight;
	if (!(root->top->leftchild)) {
		free(root->top);
		root->top = NULL;
		return top;
	}
	treepointer last = pop_pos(root);
	//printf("last is %d(%d,%d,%d)\n", last->vertex, last->weight, last->height, last->is_full);
	
	treepointer parent = root->top, child = root->top->leftchild;
	while (child) {
		if ((parent->rightchild) && (child->weight > parent->rightchild->weight)) child = parent->rightchild;
		if (last->weight <= child->weight) break;
		parent->vertex = child->vertex;
		parent->weight = child->weight;
		parent = child;
		child = parent->leftchild;
	}
	parent->vertex = last->vertex;
	parent->weight = last->weight;
	parent = last->parent;
	if (parent->rightchild) parent->rightchild = NULL;
	else parent->leftchild = NULL;
	//dfs(root->top);
	update(parent);
	//printf("end update\n");
	if (!parent) root->top = NULL;
	free(last);
	last = NULL;
	//printf("call return %d,%d\n", top->vertex, top->weight);
	return top;
}
int choose(int vertices) {
	int min = 2100000000, minpos = 0;;
	int root;
	//printf("found: ");
	//for (int i = 1; i <= found[0]; i++) {
	//	printf("%d ", found[i]);
	//}
	//printf("\n");
	for (int i = 1; i <= found[0]; i++) {
		root = found[i];
		while (heap[root]->top) {
			if (heap[heap[root]->top->vertex]->is_found) {
				free(pop(heap[root]));
				//print_heap(vertices);
			}
			else break;
		}
		//printf("%d\n",root);
		if (heap[root]->top == NULL) continue;
		//printf("top vertex is %d\n", heap[root]->top->vertex);
		if (min > (heap[root]->weight + heap[root]->top->weight)) {
			min = heap[root]->weight + heap[root]->top->weight;
			minpos = root;
		}
	}
	//printf("in choose, return %d\n", minpos);
	return minpos;
}
void shortest_path(int src, int vertices) {
	int root;
	treepointer t;
	heap[src]->is_found = TRUE;
	found[++found[0]] = src;
	for (int i = 0; i < vertices - 1; i++) {
		root = choose(vertices);
		if (!root) break;
		t = pop(heap[root]);
		heap[t->vertex]->is_found = TRUE;
		found[++found[0]] = t->vertex;
		heap[t->vertex]->weight = heap[root]->weight + t->weight;
		//print_heap(vertices);
		free(t);
		t = NULL;
	}
}

jinwhan 2년 전 0

pop_pos에서 트리 탐색하는중에 153번째줄 에서 rightchild를 leftchild로 잘못적었네요

근데 그걸 고쳐도 시간초과가 나는데 뭘 어떻게 해야할까요?

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

문제

문제

출처

ICPC

살려주십쇼 런타임에러 DoubleFree

jinwhan 2년 전 0

jinwhan 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말