글 읽기 - 시간초과 관련 질문합니다[C]

leekaejoon 5년 전 0

메모리 초과를 막기 위해 adj list를 구현하여 문제를 풀어보았는데요 메모리 이전에 너무 많은 시간을 잡아 먹어서 시간초과가 뜹니다.

혹시라도 C++ 이 아닌 C로 조건에 맞게 풀려면 어떻게 해야 할지 모르겠어서 문의드립니다.

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

typedef struct Node{
	int data;
	struct Node *next;
}Node;


typedef struct Queue 
{
	Node *front; 
	Node *rear; 
	int count;
}Queue;

void InitQueue(Queue *queue)
{
	queue->front = queue->rear = NULL; 
	queue->count = 0;
}

int IsEmpty(Queue *queue)
{
	return queue->count == 0;    
}

void Enqueue(Queue *queue, int data)
{
	Node *now = (Node *)malloc(sizeof(Node)); 
	now->data = data;
	now->next = NULL;

	if (IsEmpty(queue))
	{
		queue->front = now;   
	}
	else
	{
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}

int Dequeue(Queue *queue)
{
	int re = 0;
	Node *now;
	if (IsEmpty(queue))
	{
		return re;
	}
	now = queue->front;
	re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}

enum VisitMode { Visited = 1, NotVisited = 0 };

typedef int Element;

typedef struct tagVertex {
	Element Data;
	enum VisitMode Visited;

	int index;
	struct tagVertex * Next;
	struct tagEdge * Adjacencylist;
}Vertex;

typedef struct tagEdge {
	int Weight;
	struct tagEdge * Next;

	Vertex *From;
	Vertex *Target;
}Edge;

typedef struct tagGraph {
	Vertex * Vertices;
	int VertexCount;
}Graph;

Graph * CreateGraph() {
	Graph * NewGraph = (Graph*)malloc(sizeof(Graph));

	NewGraph->Vertices = NULL;
	NewGraph->VertexCount = 0;
	return NewGraph;
}

Vertex * CreateVertex(Element Data) {
	Vertex *NewVertex = (Vertex*)malloc(sizeof(Vertex));

	NewVertex->Adjacencylist = NULL;
	NewVertex->Next = NULL;

	NewVertex->Visited = NotVisited;
	NewVertex->Data = Data;
	NewVertex->index = -1;

	return NewVertex;
}

Edge * CreateEdge(Vertex* From, Vertex *Target, int weight) {
	Edge * NewEdge = (Edge*)malloc(sizeof(Edge));

	NewEdge->From = From;
	NewEdge->Target = Target;

	NewEdge->Next = NULL;
	NewEdge->Weight = weight;

	return NewEdge;
}
void AddVertex(Graph*G, Vertex*V) {
	Vertex*VertexList = G->Vertices;

	if (VertexList == NULL) {
		G->Vertices = V;
	}
	else {
		while (VertexList->Next != NULL)
			VertexList = VertexList->Next;

		VertexList->Next = V;

	}
	V->index = (G->VertexCount)++;
}

void AddEdge(Vertex* V, Edge *E) {
	Edge* Adjacencylist = V->Adjacencylist;
	
	if (Adjacencylist == NULL) {
		V->Adjacencylist = E;
	}
	else {
		while (Adjacencylist->Next != NULL)
			Adjacencylist = Adjacencylist->Next;

		Adjacencylist->Next = E;
	}
	
}


int shortpath(Graph *G,int *check, int start) {
	Queue * queue = (Queue*)malloc(sizeof(Queue));
	InitQueue(queue);


	int i;
	Enqueue(queue, start);
	while (!IsEmpty(queue)) {
		Vertex * v = G->Vertices;
		Edge * e = NULL;
		i = Dequeue(queue);
		while (v->Data != i) {
			v = v->Next;
		}
		e = v->Adjacencylist;
		while (e != NULL) {
			if (e->Target->Data != start) {
				Enqueue(queue, e->Target->Data);
				if (check[e->Target->Data] >= check[e->From->Data] + e->Weight)
					check[e->Target->Data] = check[e->From->Data] + e->Weight;
				else if (check[e->Target->Data] == 0)
					check[e->Target->Data] = check[e->From->Data] + e->Weight;
			}
			e = e->Next;
		}
	}
	
	return 0;
}


int main() {
	int i;
	int n, m;
	int start;
	scanf("%d" "%d" "%d", &n, &m, &start);

	Graph *graph = CreateGraph();
	Vertex* vertex = (Vertex*)malloc(sizeof(Vertex)*n + 1);
	int *check;
	check = (int*)calloc(n+1,sizeof(int));
	for (i = 0; i <=n ; i++) {
		vertex[i] = *CreateVertex(i);
	}
	for (i = 0; i <= n; i++) {
		AddVertex(graph, &vertex[i]);
	}
	for (i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d""%d""%d", &a, &b, &c);
		AddEdge(&vertex[a], CreateEdge(&vertex[a], &vertex[b], c));
	}
	shortpath(graph, check, start);
	for (i = 1; i <= n; i++) {
		if (start == i) {
			printf("0\n");
		}
		else if (check[i] == 0) {
			printf("INF\n");
		}
		else
		printf("%d\n", check[i]);
	}
	return 0;
}

djm03178 5년 전 0

리스트에 원소를 추가할 때 그 순서가 중요한 것이 아니라면, 리스트의 맨 앞에 새 노드를 끼워넣고 그 노드가 원래의 첫 노드를 가리키게 하는 방식으로 O(1)에 삽입이 가능합니다.

순서가 중요하고 맨 뒤에 끼워넣어야 하는 거라면, 맨 끝을 가리키는 포인터를 지정해서 역시 O(1)에 해결할 수 있습니다.

leekaejoon 5년 전 0

말씀해주신 조언대로 삽입 시간을 줄여보았는데요

이럼에도 불구하고 시간초과가 나오네요

오히려 제가 만든 adj list 가 인접 행렬 보다 시간을 너무 많이 잡아 먹기도 하면서 최단 경로를 찾기위해 bfs를 사용해서 그런지 1초 안에는 죽었다 깨도 안될거 같은 느낌이네요 ㅠ

한계가 여기인건지 너무 좌절스럽네요....

void AddVertex(Graph*G, Vertex*V) {
	Vertex*VertexList = G->Vertices;

	if (VertexList == NULL) {
		G->Vertices = V;
	}
	else {
		V->Next = G->Vertices;
		G->Vertices = V;
	}
	V->index = (G->VertexCount)++;
}

void AddEdge(Vertex* V, Edge *E) {
	Edge* Adjacencylist = V->Adjacencylist;

	if (Adjacencylist == NULL) {
		V->Adjacencylist = E;
	}
	else {
		E->Next = V->Adjacencylist;
		V->Adjacencylist = E;
	}
	
}

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

문제

문제

출처

ICPC

시간초과 관련 질문합니다[C]

leekaejoon 5년 전 0

djm03178 5년 전 0

leekaejoon 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말