글 읽기 - C언어 다익스트라 어디가 틀린지 모르겠습니다.

gkfkagkfka12 5년 전 0

C언어로 구현해서 좀 긴 편이지만 완벽하게 동작한다고 생각했는데 잘 안되네요.

질문검색란에 있는 대부분의 테스트 케이스까지 돌려봤고 다 맞는데 어디가 문제인지 모르겟습니다.

9%쯤에 틀립니다.

#include <stdio.h>
// vertex는 A(0)부터 시작한다.
enum { A, B, C, D, E, F, G, H, I, J, K };
const int max = 2100000000;
typedef enum { false, true } bool;

// Vertex는 정점의 번호(혹은 알파벳)와 다음 정점으로의 포인터변수 next를 가진다.
typedef struct Vertex {
	int v;
	int distance;
	int parent;
	int w;
	struct Vertex* next;
}Vertex;

// Graph는 vertex의 숫자와 인접리스트를 갖는다.
typedef struct Graph {
	int vertexNum;
	int edgeNum;
	Vertex** adj;
}Graph;

// Edge는 연결하는 두 vertex와 weight을 갖는다.
typedef struct Edge {
	int v1;
	int v2;
	int weight;
}Edge;

// vertex를 동적할당하여 리턴한다.
Vertex* CreateVertex(int v)
{
	Vertex *create = (Vertex*)malloc(sizeof(Vertex));
	create->v = v;
	create->next = NULL;
	create->w = 0;
	return create;
}

// 인접리스트를 할당한다.
Vertex** CreateAdj(int vertexNum)
{
	Vertex **adj = (Vertex**)malloc(sizeof(Vertex*)*(vertexNum + 1));
	for (int i = 1; i <= vertexNum; i++)
		adj[i] = CreateVertex(i);
	return adj;
}

// vertex를 연결하여 인접리스트를 만든다.
void ConnectVertex(Vertex** adj, int v1, int v2, int w)
{
	Vertex* current = adj[v1];
	if (current == NULL) current = CreateVertex(v1);
	else {
		while (current->next != NULL) current = current->next;
		current->next = CreateVertex(v2);
		current->next->w = w;
	}
}
int s;

// Graph를 만든다.
Graph* CreateGraph()
{
	Graph *g = (Graph*)malloc(sizeof(Graph));
	int v, e;
	scanf("%d %d", &v, &e);
	scanf("%d", &s);

	// vertex, edge의 개수 설정하고 인접 리스트, edge 배열 동적할당
	g->vertexNum = v; g->edgeNum = e;
	g->adj = CreateAdj(v);

	// 연결되는 정점과 weight을 입력하면서 다음을 진행한다.
	// 인접리스트로 vertex와 vertex를 연결한다.
	int v1, v2, w;
	for (int i = 0; i < e; i++) {
		scanf("%d%d%d", &v1, &v2, &w);
		ConnectVertex(g->adj, v1, v2, w);
	}

	return g;
}

// 메모리 해제
void Deallocation(Graph *g)
{
	for (int i = 1; i <= g->vertexNum; i++) free(g->adj[i]);
	free(g->adj);
	free(g);
}

// distance, parent의 초기화 작업
void Init_SS(Graph *g, int s)
{
	for (int i = 1; i <= g->vertexNum; i++) {
		g->adj[i]->distance = max;
		g->adj[i]->parent = NULL;
	}
	g->adj[s]->distance = 0;
}

// Relaxation 작업, distance와 parent(predecessor)를 결정한다.
void Relax(Graph *g, int u, int v, int w)
{
	if (g->adj[v]->distance > g->adj[u]->distance + w) {
		g->adj[v]->distance = g->adj[u]->distance + w;
		g->adj[v]->parent = u;
	}
}

typedef struct heap {
	int *heapTree;
	int capacity;
	int currentSize;
}Heap;

// swap 함수
void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}


// Heap을 동적 할당해서 리턴
Heap* CreateHeap(int size)
{
	Heap *h = (Heap*)malloc(sizeof(Heap));
	h->heapTree = (int*)malloc(sizeof(int)*size);
	h->capacity = size;
	h->currentSize = 0;
	return h;
}

// MinHeap에 삽입
void Insert(Heap *heap, Graph *g, Vertex *data)
{
	// 힙의 마지막 위치
	int cur = heap->currentSize;

	// 그 위치가 capacity랑 같다는 것은 이미 힙이 다 찼다는 것.
	if (cur == heap->capacity) {
		printf("힙이 가득찼습니다.");
		return;
	}

	// 가장 마지막에 데이터 삽입
	int *tree = heap->heapTree;
	tree[cur] = data->v;

	// 트리에서 부모 노드
	int parent = (cur - 1) / 2;

	// 부모노드의 값이 자식노드의 값보다 크면 바꾼 뒤에
	// 트리를 올라간다. (= 부모와 자식을 초기화한다)
	while (g->adj[tree[parent]]->distance > g->adj[tree[cur]]->distance) {
		swap(&tree[parent], &tree[cur]);
		cur = parent;
		parent = (cur - 1) / 2;
	}

	// 원소의 개수 증가
	heap->currentSize++;
}

// 힙으로 만드는 과정 (heapify)
void Heapify(Heap* heap, Graph *g)
{
	int *tree = heap->heapTree;
	// 루트노드부터 힙으로 만들어야 하므로 left child와 right child가 있다.
	int cur = 0, left, right;
	left = cur * 2 + 1;
	right = cur * 2 + 2;
	int minNode = cur;

	// currentSize는 힙에서 제일 작은 값이 삭제된 크기, 즉 이 크기 바로 직전까지 원소가 존재하므로
	// left와 right이 존재하기 위해선 이것보다 작아야 하며 left가 있어야 right이 있기 때문에 left부터 한다.
	// 반복은 child가 아예 없을 때까지.
	while (left < heap->currentSize) {
		if (g->adj[tree[cur]]->distance > g->adj[tree[left]]->distance) minNode = left;
		if (right<heap->currentSize && g->adj[tree[minNode]]->distance>g->adj[tree[right]]->distance) minNode = right;
		// cur==minNode의 의미는 child가 없다는 뜻
		if (cur == minNode) break;
		else {
			swap(&tree[cur], &tree[minNode]);
			cur = minNode;
			left = cur * 2 + 1;
			right = cur * 2 + 2;
		}
	}
}

// MinHeap에서 제거
int extractMin(Heap *heap, Graph *g)
{
	// 힙의 마지막 원소, 삽입할 때 currentSize를 증가시키기 때문에
	// 삭제할 때는 1을 빼주어야 한다. 단, 0이 아닐 경우이므로 검사 후에 빼준다.
	if (heap->currentSize == 0) {
		printf("힙이 비었습니다.");
		return;
	}
	heap->currentSize--;
	int last = heap->currentSize;
	int *tree = heap->heapTree;

	// 루트 노드의 값이 제일 작은 값이므로 루트 노드를 제거하면 간단할 것 같지만
	// 다시 힙으로 만드는데 복잡하기 때문에 마지막 원소와 바꾼다.
	swap(&tree[last], &tree[0]);
	// 리턴할 값(min) 받아온다.
	int min = tree[last];

	Heapify(heap, g);


	return min;
}

// 다익스트라 알고리즘
void Dijkstra(Graph *g, int s)
{
	// source를 제외한 distance를 무한대로, predecessor를 NIL로 초기화시키는 과정
	Init_SS(g, s);

	// 우선순위 큐에서 빠져나온 vertex를 담는 vertexList와 minHeap의 할당
	int *vertexList = (int*)malloc(sizeof(int)*(g->vertexNum + 1));
	Heap *minHeap = CreateHeap(g->vertexNum);

	// minHeap에 vertex를 전부 넣는다.
	for (int i = 1; i <= g->vertexNum; i++) Insert(minHeap, g, g->adj[i]);


	int i = 1;
	// 우선순위 큐의 크기만큼 반복
	while (minHeap->currentSize) {
		// 제일 distance가 작은 vertex를 빼서 vertexList에 넣는다.
		int u = extractMin(minHeap, g);
		vertexList[i++] = u;
		Vertex* cur = g->adj[u]->next;
		// 그 vertex에 인접한 vertex들에 대하여 relax를 하고 그와 동시에 heap을 재구성하는 heapify를 한다.
		while (cur) {
			Relax(g, u, cur->v, cur->w);
			Heapify(minHeap, g);
			cur = cur->next;
		}
	}

	// vertexList, minHeap, minHeap 안에 있는 tree에 대한 메모리 해제
	free(minHeap->heapTree);
	free(minHeap);
	free(vertexList);
}

int main(void)
{
	Graph *g = CreateGraph();
	Dijkstra(g, s);
	for (int i = 1; i <= g->vertexNum; i++) {
		if (g->adj[i]->distance == max) printf("INF\n");
		else printf("%d\n", g->adj[i]->distance);
	}

	Deallocation(g);

	return 0;
}

ehddml3 5년 전 1

Dijkstra함수 쪽에서 처음에 for문 돌리면서 모든 노드를 넣어주시는 것 같은데, 다시 사용될 가능성이 있기 때문에

Relax 가 된 이후에는 Relax되어 distance 값이 바뀐 v에 대해서 다시 Insert를 하는 과정이 필요합니다. 이런 과정을 거치게 하면 처음에는 s만 넣고 시작해도 잘 돌아갑니다.

또 그런 과정을 거치면 CreateHeap 과정에서 capacity 값을 늘려주어야 할 상황도 생길 수 있습니다. 실제로 제출 해보면 Segmentation fault가 일어나는 것 같아요.

위의 방법과 CreateHeap에서 minHeap size를 적당한 크기(size*2)로 맞춘 후에 제출해보았더니 63%정도에서 시간초과가 떴습니다.

시간 초과에 대해서는 아직 해결이 안되었네요ㄷ

gkfkagkfka12 5년 전 0

@ehddml3 시간초과는 도저히 해결못하겠는데 뭐가 문제일까요????

ehddml3 5년 전 0

다시 봐보니 vertex간의 연결관계를 Linked List로 구현하셨는데, 예를 들어 1에서 2로가는 간선이 30만개가 있다고 치면 ConnectVertex 함수에서 굉장히 많은 연산을 필요로 할 것 같습니다.

gkfkagkfka12 5년 전 0

그럼 배열로 구현하는게 나은건가요?

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

문제

문제

출처

ICPC

C언어 다익스트라 어디가 틀린지 모르겠습니다.

gkfkagkfka12 5년 전 0

ehddml3 5년 전 1

gkfkagkfka12 5년 전 0

ehddml3 5년 전 0

gkfkagkfka12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말