글 읽기 - 4%에서 에러가 발생합니다

fds252 6년 전 0

왜 오류가 생기는지 도저히 이해가 안갑니다.

BFS로 탐색하면서 깊이를 계산합니다.

1번 노드에서 가장 멀리 떨어진 노드를 찾고,

그 노드에서 가장 멀리 떨어진 노드 깊이를 출력합니다.

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

#define TRUE 1
#define FALSE 0
#define MAX_N 100000

typedef struct _listnode {
	int number;
	int cost;
	struct _listnode *next;
} ListNode;

typedef struct _list {
	int size;
	struct _listnode *head;
	struct _listnode *tail;
} List;

typedef struct _node {
	int number;
	int depth;
	int isVisited;
	List *edge;
} Node;


int queue[MAX_N];
int front, rear;

int n; 
Node *node[MAX_N];
int maxDepth, maxNode;

void init_queue();
void addList(List *l, ListNode *src);
void clearList(List *l);
void put(int data);
void traverseBFS();

int main(void) {
	init_queue();
	int i, num_src, num_dest, cost;
	scanf("%d", &n);
	for(i=0; i<n; i++) {
		node[i] = (Node *)malloc(sizeof(Node));
		node[i]->number = i+1;
		node[i]->isVisited = FALSE;
		node[i]->edge = (List *)malloc(sizeof(List));
		node[i]->edge->size = 0;
		node[i]->edge->head = NULL;
		node[i]->edge->tail = NULL;
	}
	
	for(i=0; i<n; i++) {
		scanf("%d", &num_src);
		while(1) {
			scanf("%d", &num_dest);
			if(num_dest == -1)	break;
			scanf("%d", &cost);
			
			ListNode *new_node1 = (ListNode *)malloc(sizeof(ListNode));
			new_node1->number = num_src;
			new_node1->cost = cost;
			addList(node[num_dest-1]->edge, new_node1);
			
			ListNode *new_node2 = (ListNode *)malloc(sizeof(ListNode));
			new_node2->number = num_dest;
			new_node2->cost = cost;
			addList(node[num_src-1]->edge, new_node2);
		}
	}
	
	maxDepth = 0;
	node[0]->depth = 0;
	put(1);
	traverseBFS();
	
	//printf("%d ", maxNode);
	
	for(i=0; i<n; i++) {
		node[i]->isVisited = FALSE;
	}
	maxDepth = 0;
	node[maxNode-1]->depth = 0;
	put(maxNode);
	traverseBFS();
	
	//printf("%d\n", maxNode);
	printf("%d\n", maxDepth);
	for(i=0; i<n; i++) {
		clearList(node[i]->edge);
		free(node[i]);
	}
	return 0;
}

void addList(List *l, ListNode *src) {
	l->size++;
	if(l->head == NULL) {
		l->head = src;
		l->tail = src;
		return;
	}
	l->tail->next = src;
	l->tail = src;
}

void clearList(List *l) {
	ListNode *temp = l->head;
	ListNode *deleter;
	int i;
	for(i=0; i<l->size; i++) {
		deleter = temp;
		temp = temp->next;
		free(deleter);
	}
	free(l);
}

void init_queue() {
	front = 0;
	rear = 0;
}

int isQueueEmpty() {
	if(front == rear)	return TRUE;
	return FALSE;
}

void put(int data) {
	queue[rear] = data;
	rear = ++rear%MAX_N;
}

int get() {
	int temp = queue[front];
	front = ++front%MAX_N;
	return temp;
}

void expandNode(Node *src) {
	src->isVisited = TRUE;
	if(src->depth > maxDepth) {
		maxDepth = src->depth;
		maxNode = src->number;
	}
	int i;
	ListNode *temp = src->edge->head;
	for(i=0; i<src->edge->size; i++) {
		if(node[temp->number-1]->isVisited == FALSE)	node[temp->number-1]->depth = src->depth + temp->cost;
		temp = temp->next;
	}
}

void traverseBFS() {
	int i, temp_pop;
	ListNode *temp_ptr;
	while(isQueueEmpty() != TRUE) {
		temp_pop = get();
		expandNode(node[temp_pop-1]);
		temp_ptr = node[temp_pop-1]->edge->head;
		for(i=0; i<node[temp_pop-1]->edge->size; i++) {
			if(node[temp_ptr->number-1]->isVisited == FALSE)	put(temp_ptr->number);
			temp_ptr = temp_ptr->next;
		}
	}
}

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

문제

문제

출처

ICPC

4%에서 에러가 발생합니다

fds252 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말