글 읽기 - 11%에서 자꾸 틀립니다.

hyunbinny 1년 전 0

에제와 질문게시판에 있는 반례 모두 정확하게 나오는데 자꾸 틀렸다고 나옵니다.
혹시 질문게시판의 반례 말고 다른 반례를 알 수 있을까요..?
(현재 자료구조/알고리즘 구조를 익히는 중이라 가급적이면 C++보다는 C언어로 해결하고자 합니다.)
#include <stdio.h>
#include <stdlib.h>

typedef enum visitMode 
{visited, notVisited}
Mode;
typedef int ElementType;
typedef struct tagVertex
{
	ElementType data;
	Mode visit;
	int index;

	struct tagEdge *adjList;
	struct tagVertex *next;
} Vertex;
typedef struct tagEdge
{
	Vertex *from;
	Vertex *target;
	struct tagEdge *next;
} Edge;
typedef struct tagGraph
{
	Vertex *vertices;
	int vCount;
} Graph;
typedef struct tagNode
{
	Vertex *data;
	struct tagNode *next;
} Node;
typedef struct tagQueue
{
	Node *front;
	Node *rear;
	int count;
} Queue;
typedef struct tagInput
{
	int from;
	int target;
} Input;

Edge *createEdge(Vertex *from, Vertex *target)
{
	Edge *newEdge = (Edge *)malloc(sizeof(Edge));

	newEdge->from = from;
	newEdge->target = target;
	newEdge->next = NULL;

	return newEdge;
}
void destroyEdge(Edge *edge)
{
	free(edge);
}
Vertex *createVertex(ElementType newData)
{
	Vertex *newVertex = (Vertex *)malloc(sizeof(Vertex));

	newVertex->data = newData;
	newVertex->index = -1;
	newVertex->visit = notVisited;

	newVertex->next = NULL;
	newVertex->adjList = NULL;

	return newVertex;
}
void destroyVertex(Vertex *vertex)
{
	Edge *current = vertex->adjList;
	Edge *next;

	while (current != NULL)
	{
		next = current->next;
		destroyEdge(current);
		current = next;
	}
	free(vertex);
}
Graph *createGraph(void)
{
	Graph *newGraph = (Graph *)malloc(sizeof(Graph));

	newGraph->vertices = NULL;
	newGraph->vCount = 0;

	return newGraph;
}
void destroyGraph(Graph *graph)
{
	Vertex *current = graph->vertices;
	Vertex *next;

	while (current != NULL)
	{
		next = current->next;
		destroyVertex(current);
		current = next;
	}
}

void addEdge(Vertex *vertex, Edge *newEdge)
{
	Edge *current = vertex->adjList;

	if (current == NULL)
	{
		vertex->adjList = newEdge;
	}
	else {
		while (current->next != NULL)
		{
			current = current->next;
		}
		current->next = newEdge;
	}
}
void addVertex(Graph *graph, Vertex *newVertex)
{
	Vertex *current = graph->vertices;

	if (current == NULL)
	{
		graph->vertices = newVertex;
	}
	else {
		while (current->next != NULL)
		{
			current = current->next;
		}
		current->next = newVertex;
	}
	newVertex->index = graph->vCount++;
}
void printGraph(Graph *graph)
{
	Vertex *vertex = NULL;
	Edge *edge = NULL;

	if ((vertex = graph->vertices) == NULL)
		return;

	while (vertex != NULL)
	{
		printf("%d: ", vertex->data);

		if ((edge = vertex->adjList) == NULL)
		{
			vertex = vertex->next;
			printf("\n");
			continue;
		}

		while (edge != NULL)
		{
			printf("%d ", edge->target->data);
			edge = edge->next;
		}

		printf("\n");
		vertex = vertex->next;
	}

	printf("\n");
}
Node *createNode(Vertex *newData)
{
	Node *newNode = (Node *)malloc(sizeof(Node));

	newNode->data = newData;
	newNode->next = NULL;

	return newNode;
}
void destroyNode(Node *node)
{
	free(node);
}
int isEmpty(Queue *queue)
{
	return (queue->front == NULL);
}
void enqueue(Queue *queue, Node *newNode)
{
	if (queue->front == NULL)
	{
		queue->front = newNode;
		queue->rear = newNode;
	}
	else
	{
		queue->rear->next = newNode;
		queue->rear = newNode;
	}
	queue->count++;
}
Node *dequeue(Queue *queue)
{
	Node *remove = queue->front;

	if (isEmpty(queue))
		return NULL;

	if (queue->front->next == NULL)
	{
		queue->front = NULL;
		queue->rear = NULL;
	}
	else
	{
		queue->front = queue->front->next;
	}
	queue->count--;

	return remove;
}
Queue *createQueue(void)
{
	Queue *newQueue = (Queue *)malloc(sizeof(Queue));

	newQueue->front = NULL;
	newQueue->rear = NULL;
	newQueue->count = 0;

	return newQueue;
}
void destroyQueue(Queue *queue)
{
	while (!isEmpty(queue))
	{
		Node *popped = dequeue(queue);
		destroyNode(popped);
	}
	free(queue);
}

int compare(const void *_elem1, const void *_elem2)
{
	Input *elem1 = (Input *)_elem1;
	Input *elem2 = (Input *)_elem2;

	if (elem1->target > elem2->target)
	{
		return 1;
	}
	else if (elem1->target < elem2->target)
	{
		return -1;
	}
	else {
		if (elem1->from > elem2->from)
			return 1;
		else if (elem1->from < elem2->from)
			return -1;
		return 0;
	}
	return 0;
}
void dfs(Vertex *v)
{
	Edge *e = NULL;

	printf("%d ", v->data);
	v->visit = visited;
	e = v->adjList;

	while (e != NULL)
	{
		if (e->target != NULL && e->target->visit == notVisited)
		{
			dfs(e->target);
		}
		e = e->next;
	}
}
void bfs(Vertex *v, Queue *queue)
{
	Edge *e = NULL;

	printf("%d ", v->data);
	v->visit = visited;
	enqueue(queue, createNode(v));

	while (!isEmpty(queue))
	{
		Node *popped = dequeue(queue);
		v = popped->data;
		e = v->adjList;

		while (e != NULL)
		{
			v = e->target;
			if (v != NULL && v->visit == notVisited)
			{
				printf("%d ", v->data);
				v->visit = visited;
				enqueue(queue, createNode(v));
			}
			e = e->next;
		}
	}

	printf("\n");
}
int main(void)
{
	int vCount, eCount, start;
	Graph *graph = createGraph();
	Queue *queue = createQueue();
	Vertex *v[1001];
	Input arr[10001];

	// 그래프 정점 생성
	scanf("%d%d%d", &vCount, &eCount, &start);
	for (int i = 0; i < vCount; i++)
	{
		v[i] = createVertex(i+1);
		addVertex(graph, v[i]);
	}

	// 그래프 간선값 입력 및 오름차순 정렬
	for (int i = 0; i < eCount; i++)
	{
		scanf("%d%d", &arr[i].from, &arr[i].target);
		qsort(arr, i+1, sizeof(Input), compare); 
	}

	// 그래프 간선 추가
	for (int i = 0; i < eCount; i++)
	{
		int from = arr[i].from-1;
		int target = arr[i].target-1;

		addEdge(v[from], createEdge(v[from], v[target]));
		addEdge(v[target], createEdge(v[target], v[from]));
	}

	// 깊이우선탐색 및 순위 설정
	dfs(v[start-1]);
	printf("\n");

	for (int i = 0; i < vCount; i++)
	{
		v[i]->visit = notVisited;
	}
	bfs(v[start-1], queue);

	// 메모리 할당 해제
	destroyQueue(queue);
	destroyGraph(graph);
	exit(0);
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

11%에서 자꾸 틀립니다.

hyunbinny 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
